Google Interview Question
Site Reliability EngineersCountry: United States
Interview Type: In-Person
OK, here is a solution using BFS.
Note that I abstracted away things like dictionary representation and getting all the words that differ from the given word in just one character. There are several different ways to implement these and there's no point polluting the solution with unnecessary detail. Plus a few people before me have code snippets that could be used for that.
If you are really going read this, I'd suggest to paste the code into Visual Studio (or your favorite editor that has syntax highlighting).
#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
// Hash table? Trie? BST? Your choice :-)
class Dictionary
{
public:
Dictionary(string path);
~Dictionary();
// Generate the next word that differs from s only in s[position].
// If there are no such words, s is returned.
// Repeatedly calling this function will eventually return the
// string that we started with.
// One possible implementation of this is to increment s[position]
// mod 26 until a word in the dictionary is found.
const string & GetNextWord(string s, int position) const;
};
bool FindPath(
const Dictionary * pDict,
string start,
string end,
map<string, string> & mpCP)
{
mpCP[start] = ""; // Put start in the map with empty parent
queue<string> q;
q.push(start); // Enqueue start
int length = start.size();
//
// Repeat until we found end or until no more words left
while(!q.empty())
{
// Get the next word from the queue
string word = q.front();
q.pop();
// Because of the early out below, this can only happen when start==end
if (word == end)
return true;
//
// Generate all possible children (that we have not seen before)
// and put them in the queue
for (int i = 0; i < length; ++i)
{
string s = word;
while ((s = pDict->GetNextWord(s, i)) != word)
{
// We have already seen this word, do nothing
if (mpCP.count(s) > 0)
continue;
// We have not yet seen this word, let's add it
// to the map (with its parent) and to the queue
mpCP[s] = word;
// Early out - we found our target!!!
if (s == end)
return true;
q.push(s);
}
}
}
return false;
}
// Print path (up to word end) using entries in the map
void PrintPath(const map<string, string> & mpCP, const string & end)
{
string parent = mpCP.find(end)->second;
if (parent != "")
{
PrintPath(mpCP, parent);
cout << " -> " << end;
}
}
int main()
{
string start = "CAT";
string end = "DOG";
if (start.size() != end.size())
{
cout << "String lengths don't match, exiting ..." << endl;
return 1;
}
Dictionary dict("FileWithAllWords.txt");
map<string, string> mpChildParent;
bool success = FindPath(&dict, end, -1, mpChildParent, q);
if (success)
{
cout << "Path from " << start << " to " << end << " exists!" << endl;
cout << start;
PrintPath(mpChildParent, end);
}
else
{
cout << "Path from " << start << " to " << end << " does not exist!" << endl;
}
return 0;
}
Which data structure is used to maintain the dictionary? or the words in the dictionary are just stored in a file?
From a graph out of the words, word A is adjacent to word B if replacing one character in one gives the other.
Now do a "double" breadth first search, starting a the source and the target. (i.e you start two independent BFS, one from source and one from target, stopping when they meet).
From yur explanation i can get the distance between these two words , but how can i get all the legitimate words during the transformation?
Thanks for the reply. if you have a link for the dictionary representation as graph, please post it.. i just wanted to see how the nodes are connected..
@Vikas, BFS is more quick, O(n), Dijkstra is O(n^2), because we don't need one node to all nodes, so BFS is enough
def is_in_Dictionary(dic_word):
<CODE TO CHECK WHTHER THE WORD IS IN DICTIONARY>
def find_cloneWord(w1, w2):
for i in range(sw1)
sw1_d = sw1
for j in range(sw2):
sw2_d = sw2
sw2_d[j] = sw1_d[i]
dic_word = ''.join(sw2_d)
if is_in_Dictionary(dic_word) == 1:
print dic_word
num_words = num_words + 1
else:
print "No Word in Dictionary"
#Main Function
w1 = "DAMP"
w2 = "LIKE"
sw1 = w1.strip()
sw2 = w2.strip()
num_words = 0
Java Solution
Assuming the dictionary is a set of strings, make a HashSet<char[]> and implement a method to find the next change need that returns null if no possible change. Iterate through the char[] of the input, or you can also iterate while the char[] inputs are not equal.
public static List<String> getChanges(String first, String last, Set<String> dict) {
Set<char[]> charDict = new HashSet<char[]>();
for (String word : dict) {
charDict.add( word.toCharArray() );
}
char[] from = first.toCharArray();
char[] to = last.toCharArray();
List<String> changes = new LinkedList<String>();
while (! from.equals(to)) { //array equality
changes.add(from.toString());
from = next(from, to, dict);
if (from == null)
return null;
}
changes.add( to.toString() );
return changes;
}
public static char[] next(char[] from, char[] to, Set<char[]> dict) {
for (int i =0; i < to.length; i++) {
if ( from[i] != to[i] ) {
char temp = from[i];
from[i] = to[i];
if ( dict.contains(from) )
return from;
from[i] = temp;
}
}
if (!from.equals(to))
return null;
else
return to;
}
Can't edit posts? Wow, well there are some simple errors in there such as
from = next(from, to, dict)
which should be
from = next(from, to, charDict)
I'm sure there is more, as I didn't put this through a compiler or anything, but you get the gist of things
2 solutions. First approach is the most scalable one:
Approach 1:
Preprocessing step: Create a graph of all the words in the dictionary such there is an edge between word X to Y only when they differ by one character replacement only.
1. Find the source word in graph.
2. From the source node run a BFS to find the target node.
Approach 2:
1. Do a BFS, but this time you have to generate all posible states at each step, so there would be additional cost of looking up the word in the dictionary.
Time complexity= O(n^n)
Well in 1st approach you would start from DAMP and generate following in the first step:
LAMP,DIMP,DAKP and DAME, and at the same time look up each of them in the dictionary, and proceed only with those nodes that exist in the dictionary.
While in approach 1 you already know what words could be obtained with one replacement exist, so you don't have to generate n combinations and don't have to lookup each of them in the dictionary at each step because you have direct nodes that you can follow.
static void Main(string[] args)
{
string starttstr = "DAMP";
string entstr = "LIKE";
string path = "Dictionary.txt";
try
{
var steps = GetSteps(starttstr, entstr, path);
foreach (var step in steps) {
Console.Write("{0}->", step.ToUpper());
}
Console.Write("\b\b \n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
Console.ReadKey();
}
/// <summary>
/// Creating steps from starttstr to entstr and sherching this in dictionary file by path
/// </summary>
/// <param name="starttstr"></param>
/// <param name="entstr"></param>
/// <param name="path"></param>
/// <returns></returns>
private static IEnumerable<string> GetSteps(string starttstr, string entstr, string path)
{
if ( entstr == null )
{
throw new ArgumentNullException("entstr");
}
if ( starttstr == null )
{
throw new ArgumentNullException("starttstr");
}
if ( path == null )
{
throw new ArgumentNullException("path");
}
if ( starttstr.Length != entstr.Length )
{
throw new Exception("Start and End strings not equals by length");
}
string basestring = starttstr;
var result = new List<string> {starttstr};
while (entstr.ToUpper() != basestring.ToUpper())
{
var word = SearchWord(basestring,result,path);
if (word != null)
{
result.Add(word);
basestring = word;
}
else {
result.Add("Next step is not found");
return result;
}
}
return result;
}
/// <summary>
/// Searching first word in dictionary which has one different letter
/// </summary>
/// <param name="basestring"></param>
/// <param name="arraystr">latest founded strings</param>
/// <param name="path">path to dictionary file</param>
/// <returns>founded string or null if string is not found</returns>
/// <exception cref="FileNotFoundException"></exception>
private static string SearchWord( string basestring, IEnumerable<string> arraystr,string path )
{
if(!File.Exists(path))
{
throw new FileNotFoundException("Dictionary ia not found",path);
}
using (var reader = new StreamReader(path))
{
while (!reader.EndOfStream)
{
var line = reader.ReadLine();
if ( !string.IsNullOrEmpty(line) )
{
if (CompareStrings(basestring, line) == 1 && arraystr.All(str=>str.ToUpper()!=line.ToUpper()))
{
return line;
}
}
}
return null;
}
}
/// <summary>
/// Compare two strings
/// </summary>
/// <param name="str1"></param>
/// <param name="str2"></param>
/// <returns>Quantity of differents betwen strings or -1 if strings have different length</returns>
/// <exception cref="ArgumentNullException"></exception>
static int CompareStrings(string str1, string str2)
{
if ( str1 == null )
{
throw new ArgumentNullException("str1");
}
if ( str2 == null )
{
throw new ArgumentNullException("str2");
}
if(str1.ToUpper()==str2.ToUpper())
{
return 0;
}
if(str1.Length!=str2.Length)
{
return -1;
}
var ar1 = str1.ToUpper().ToCharArray();
var ar2 = str2.ToUpper().ToCharArray();
int comparecounter=0 ;
for (int i = 0; i < ar1.Count(); i++)
{
if(ar1[i]!=ar2[i])
{
comparecounter++;
}
}
return comparecounter;
}
This is a DFS problem.
Form a graph of all the words in the dictionary. Each word will be a node, and there will be edges between two words which differ by a character only. Now start from the source string, and find all paths to the target string. DFS.
If the question was to find the shortest path to the target, you'd use BFS.
The question does not specify anything about the shortest path. It only asks us to find a path. There can be several such path. Hence, I said DFS. You could clarify this with the interviewer.
If you create separate trees based on the number of characters, it would optimize the solution. As per my understanding the number of characters in input and output has to be same...so creating separate trees would help.
Here's an implementation that does what I explained above. Exploring all paths. Maybe can be optimized further:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void print(vector<string> list)
{
for(int i = 0; i<list.size(); i++)
cout << list[i] << " ";
cout << endl;
}
void findPath(string input, string output, vector<string> dict, vector<string> list)
{
if(input == output)
{
list.push_back(output);
print(list);
return;
}
for(int i = 0; i< input.length(); i++)
{
for(int j = 0; j < 26; j++)
{
char ch = 'a' + j;
if(input[i] != ch)
{
char temp = input[i];
input[i] = ch;
if(find(dict.begin(), dict.end(), input) != dict.end() && find(list.begin(), list.end(), input) == list.end())
{
input[i] = temp;
list.push_back(input);
input[i] = ch;
findPath(input, output, dict, list);
input[i] = temp;
list.pop_back();
}
else
{
input[i] = temp;
}
}
}
}
}
int main(int argc, char **argv)
{
int n;
string input, output;
getline(cin, input);
getline(cin, output);
string dummy;
cin >> n;
getline(cin, dummy);
string word;
vector<string> dict;
for(int i =0; i<n; i++)
{
getline(cin,word);
dict.push_back(word);
}
vector<string> list;
findPath(input, output, dict, list);
}
The problem could be modeled as a graph traversal (DFS or BFS), but in my opinion it's going to be complicated to implement.
My solution instead is:
public static void findPath(String str, Dictionary dict, int pos, String dest, List<String> list) {
if (str == null || dict == null) return;
if (pos < 0 || pos >= str.size()) return;
if (dest.equals(str)) print(list);
for(Char ch : getChars()) {
str = str.replace(pos, ch);
if (!dict.contains(str)) continue;
findPath(str, pos+1, dest, list.add(str);
}
}
Essentially, given the starting string I explore sistematically all the valid paths.
This doesn't handle the case when the first change of the only solution is to change a character not in the first index or the character in a position needs to be changed multiple times during the conversion.
{
const int strlength = 100;
char sourceStr [strlength] = {'\0'};
char destStr [strlength] = {'\0'};
int nStr = 0;
char temp;
bool fRestart = true; // variable to be checked at the end of loop to see whether rerun is required
cout <<"\nEnter source sring: ";
cin >> sourceStr;
cout <<"\nEnter destination sring: ";
cin >> destStr;
nStr = strlen(sourceStr);
cout << "\nString Conversion Process: " << sourceStr;
while (fRestart)
{
fRestart = false;
for (int i = 0; i < nStr; i++)
{
temp = sourceStr[i];
if (sourceStr[i] != destStr[i])
{
sourceStr[i] = destStr[i];
if (false == isValidWord(sourceStr)) // isvalid checks dictionary, if the wor is valid
{
sourceStr[i] = temp;
fRestart = true;
}
else
{
cout << " -> " << sourceStr;
}
}
}
};
}
I believe this would work
int tbool=0,i=0,changed=0,count=0;
if(strlen(src)==strlen(dest))
{
int len=strlen(src);
char* str=new char[len];
int* modified=new int[strlen(src)];
count=2*len;
for(i=0;i<len;i++)
{
modified[i]=0;
}
//Changing the source
strcpy(str,src);
while(strcmp(str,dest)&& count>0)
{
for(i=0;i<len;i++)
{
if(src[i]!=dest[i]&& modified[i]!=1 )
{
str[i]=dest[i];
if(dic.find(str))
{
modified[i]=1;
cout<<str<<endl;
changed++;
count--;
}
else
str[i]=src[i];
}
else if(src[i]==dest[i])
{
modified[i]=1;
changed++;
count--:
}
}
}
if(count==0)
cout<<"Could not convert from source to destination in limited span";
}
else
cout<<"String length not equal";
This doesn't handle the case when the first change of the only solution is to change one of the characters in source string to a character different to the character in the same position of destination string.
A few comments ...
DFS - you would run out of memory very quickly because the recursion tree can be as deep as the number of words of given length in the dictionary. Plus you'd need to remember which words you had already visited to avoid visiting them repatedly with different prefixes.
BFS - that seems to be the only reasonable solution. The difficult part is doing BFS efficiently using a reasoably clean code.
If you doing anything else, seemingly clever, make sure that your code works for the 2 examples. And please add some explanation/comments (@Sunny and others). Blasting code on the page without any explanation is not helping anybody.
Fast fastest solution that does not use graph for DFS. For dictionary with 120K words solution for EVERY input can be obtained in 0.12sec.
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>
using namespace std;
static constexpr int alphabetSize = 'z' - 'a' + 1;
class FinderResult {
public:
FinderResult & operator <<(string s) {
sequence.push_back(s);
return *this;
}
void outputToStream(ostream &out) const {
if (sequence.size() == 0) {
out << "(not found)";
} else {
for (const string &s : sequence) {
out << s;
if (&s != &sequence.back()) {
out << ", ";
}
}
}
}
private:
vector<string> sequence;
};
ostream & operator <<(ostream &out, const FinderResult &result) {
result.outputToStream(out);
return out;
}
class MaskCache {
public:
vector<int> indices;
};
class PositionCache {
public:
map<string, MaskCache> mask;
};
class Dictionary {
public:
Dictionary & operator <<(string word) {
int wordIndex = size();
for (int position = 0; position < length_; position++) {
char saved = word[position];
word[position] = '*';
PositionCache &positionCache = positions[position];
auto iterator = positionCache.mask.find(word);
if (iterator == positionCache.mask.end()) {
MaskCache maskCache;
maskCache.indices.push_back(wordIndex);
positionCache.mask.insert(std::make_pair(word, maskCache));
} else {
iterator->second.indices.push_back(wordIndex);
}
word[position] = saved;
}
words.push_back(word);
return *this;
}
void init(int length) {
length_ = length;
positions.resize(length);
}
string & operator [](int index) {
return words[index];
}
int size() {
return words.size();
}
private:
// cache
int length_;
public:
vector<string> words;
vector<PositionCache> positions;
};
class Finder {
public:
Finder(string fromString, string toString) : fromString_(fromString), toString_(toString) {
}
void load() {
length_ = fromString_.size();
dictionary_.init(length_);
ifstream dictionaryFile("EnglishWords");
string word;
while (!dictionaryFile.eof()) {
dictionaryFile >> word;
if (word.size() == fromString_.size()) {
int wordIndex = dictionary_.size();
if (fromString_ == word) {
fromIndex_ = wordIndex;
}
if (toString_ == word) {
toIndex_ = wordIndex;
}
dictionary_ << word;
}
}
visited_ = vector<bool>(dictionary_.size(), false);
sequence_ = vector<string>();
}
FinderResult find() {
FinderResult result;
if (fromIndex_ != -1 && toIndex_ != -1) {
if (fromIndex_ == toIndex_) {
result << fromString_;
} else {
bool found = internalFind(fromIndex_);
if (found) {
result << dictionary_[fromIndex_];
for (int i = sequence_.size() - 1; i >= 0; i--) {
result << sequence_[i];
}
}
}
}
return result;
}
protected:
bool internalFind(int wordIndex) {
if (visit(wordIndex)) {
if (wordIndex == toIndex_) {
return true;
} else {
for (int position = 0; position < length_; position++) {
string ¤tString = dictionary_[wordIndex];
PositionCache &positionCache = dictionary_.positions[position];
if (!positionCache.mask.empty()) {
char saved = currentString[position];
currentString[position] = '*';
auto maskCacheIterator = positionCache.mask.find(currentString);
if (maskCacheIterator != positionCache.mask.end()) {
vector<int> &indices = maskCacheIterator->second.indices;
for (int index : indices) {
if (internalFind(index)) {
sequence_.push_back(dictionary_[index]);
currentString[position] = saved;
return true;
}
}
}
currentString[position] = saved;
}
}
}
}
return false;
}
bool visit(int index) {
if (visited_[index]) {
return false;
} else {
visited_[index] = true;
return true;
}
}
private:
// cache
int length_;
string fromString_;
string toString_;
vector<bool> visited_;
vector<string> sequence_;
int fromIndex_ = -1;
int toIndex_ = -1;
Dictionary dictionary_;
};
int main(int argc, char **argv) {
if (argc < 3 || argc > 4) {
cout << "Wrong count of arguments, should be 2 or 3, given " << argc - 1 << endl;
return -1;
} else {
Finder finder(argv[1], argv[2]);
finder.load();
FinderResult result;
result = finder.find();
if (argc == 4 && argv[3][0] == '1') {
cout << "Result: " << result << endl;
}
}
}
Here's my DFS in Racket Scheme:
#lang racket
(define (match? src str)
(and (= (string-length src)
(string-length str))
(= 1
(count identity
(map (lambda (lhs rhs) (not (eq? lhs rhs)))
(string->list src)
(string->list str))))))
(define (solve src dst words)
(let solve* ((src src)
(words words)
(path '()))
(cond [(equal? src dst) (cons #t (cons src path))]
[(null? words) (cons #f path)]
[else (call/cc
(lambda (return)
(let ([words (remove src words)])
(for-each (lambda (word)
(let* ([path (cons src path)]
[result (solve* word words path)])
(when (car result)
(return (cons #t (cdr result))))))
(filter ((curry match?) src) words)))
(cons #f path)))])))
(let* ([src "cat"]
[dst "dog"]
[words '("cat" "cot" "bat" "dog" "dot")]
[result (solve src dst words)])
(if (car result)
(printf "~a~%" (reverse (cdr result)))
(printf "failed~%")))
My C++ code here. Solved in DFS style, heavily depends on Boost and STL to shorten the code.
The input file:
cat dot
cat cot dot dog
Here's the code:
#include <boost/bind.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/istream_range.hpp>
using namespace boost;
using namespace boost::adaptors;
using namespace std;
bool match (string const& lhs, string const& rhs)
{
if (lhs.length () != rhs.length ())
return false;
auto pos = mismatch (lhs, rhs);
if (pos.first == lhs.cend ())
return false;
pos = mismatch (make_iterator_range (pos.first + 1, lhs.cend ()),
make_iterator_range (pos.second + 1, rhs.cend ()));
return pos.first == lhs.cend ();
}
template <
typename ForwardTraversalRange,
typename OutputIterator
>
bool solve (string const& src,
string const& dst,
ForwardTraversalRange words,
OutputIterator output)
{
if (src == dst)
return true;
if (empty (words))
return false;
vector<string> candidates;
auto pred = bind (match, _1, src);
copy (words | filtered (pred), back_inserter (candidates));
for (auto word : candidates) {
vector<string> new_words;
auto pred = bind (not_equal_to<string> (), _1, src);
copy (words | filtered (pred), back_inserter (new_words));
if (solve (word, dst, new_words, output)) {
*output = word;
return true;
}
}
return false;
}
int main (int argc, char* argv [])
{
string src, dst;
vector<string> words;
cin >> src >> dst;
copy (istream_range<string> (cin), back_inserter (words));
vector<string> path;
solve (src, dst, words, back_inserter (path));
path.push_back (src);
copy (path | reversed, ostream_iterator<string> (cout, "\n"));
return 0;
}
a.) Assume that we have a function that returns a list of words that differ from the given word by a single character.
b.) The distance metric between two words is the number of characters that they differ in.
c.) We can use a linked list to store the sequence of words that were found to help reach the destination.
Now,
1.) starting from the destination find 'all the words' that are at the distance of 1 from the 'current' word.
2.) Find the word from the list such that the sum of the distances of the word from the destination is closest to the distance between the source and the destination.
3.) If the list was empty before step 2.) then backtrack and regenerate the list for the previous word chosen and then choose another word fulfilling the criteria mentioned in step 2.)
4.) Repeat the above process till you reach a destination or till you cannot find another word in a list that you haven't visited. In which case there is no way you can reach the destination.
I guess the time complexity of the above approach would be poor. But it can have an acceptable space complexity since you would be regenerating the lists if you backtrack.
However, I think the approach should work, nonetheless.
Don't use a generic BFS, use A* search. You use the edit distance of each candidate on the horizon to the target as the heuristic. That way you're not searching blindly with BFS. Maintain the dictionary in a trie that supports wildcard search (wildcard char matches any character, go down all branches).
My native idea.
2.h, header file for a simple dict implementation with a hash table
// 2.h
#include <string>
#include <map>
class Dict {
private:
static std::map<std::string, int> ht_;
static bool inited_;
public:
static bool has(const std::string& word);
};
2.cpp, impelmentation file
#include "2.h"
std::map<std::string, int> Dict::ht_;
bool Dict::inited_ = false;
bool Dict::has(const std::string& word)
{
if (!inited_) {
inited_ = true;
ht_["COT"] = 1;
ht_["DOT"] = 1;
ht_["COG"] = 1;
}
return ht_.find(word) != ht_.end();
}
main file
#include "2.h"
#include <stdio.h>
#include <string.h>
int foo(size_t pos, char *src, const char *dest)
{
static int count = 0;
printf("calling %d\n", ++count);
if (strcmp(src, dest) == 0) {
printf("%s\n", src);
return 0;
}
char temp;
for (size_t i = pos, l = strlen(dest); i < l; i++) {
if (src[i] == dest[i]) {
printf("%s\n", src);
continue;
}
temp = src[i];
src[i] = dest[i];
if (Dict::has(src)) {
printf("%s\n", src);
return foo(i + 1, src, dest);
} else {
src[i] = temp;
continue;
}
}
return 0;
}
int main()
{
char src[] = "CAT", dest[] = "DOG";
printf("%s\n", src);
foo(0, src, dest);
printf("%s\n", dest);
return 0;
}
#include <queue>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <stack>
struct Node
{
std::string parentData;
std::set<Node> adjacentNodes;
std::string data;
explicit Node(const std::string& dat) : data(dat)
{}
bool operator< (const Node& rhs) const { return data < rhs.data; }
};
struct DictionaryGraph
{
std::unordered_set<std::string> dictionary;
std::unordered_map<std::string, Node> graph;
explicit DictionaryGraph(const std::unordered_set<std::string>& dict)
: dictionary(dict)
{
for( const auto& word : dictionary )
{
Node node(word);
std::set<Node> adjacent_nodes;
for( auto change_char = 'A'; change_char <= 'Z'; ++change_char )
{
if( change_char != word[0] )
{
std::string to_find(change_char + word.substr(1,2));
const auto& found = dictionary.find(to_find);
if( found != dictionary.end() )
{
adjacent_nodes.insert(Node(to_find));
}
}
if( change_char != word[1] )
{
std::string to_find(word.substr(0, 1) + change_char + word.substr(2,1));
if( dictionary.find(to_find) != dictionary.end() )
{
adjacent_nodes.insert(Node(to_find));
}
}
if( change_char != word[2] )
{
std::string to_find(word.substr(0, 2) + change_char);
if( dictionary.find(to_find) != dictionary.end() )
{
adjacent_nodes.insert(Node(to_find));
}
}
}
node.adjacentNodes = adjacent_nodes;
graph.insert(std::make_pair(word, node));
}
}
};
void BreadthFirstSearch( const Node& root, const std::string& target, std::unordered_map<std::string, Node>& graph )
{
std::cout << "start:" << root.data << " target:" << target << "\n";
std::unordered_set<std::string> visited;
std::queue<Node> node_queue;
node_queue.push(root);
visited.insert(root.data);
while( !node_queue.empty() )
{
Node current_node = node_queue.front();
node_queue.pop();
if( current_node.data == target )
{
std::cout << "Found target:" << current_node.data << std::endl;
std::stack<std::string> route;
route.push(current_node.data);
while( !current_node.parentData.empty() )
{
route.push(current_node.parentData);
if( graph.find(current_node.parentData) != graph.end() )
{
current_node = graph.find(current_node.parentData)->second;
}
else
{
break;
}
}
if( !route.empty() )
{
std::cout << route.top();
route.pop();
}
while( !route.empty() )
{
std::cout << "->" << route.top();
route.pop();
}
break;
}
for( auto& node : current_node.adjacentNodes )
{
if( visited.find(node.data) == visited.end() )
{
Node& graph_node = graph.find(node.data)->second;
graph_node.parentData = current_node.data;
node_queue.push( graph_node );
visited.insert(node.data);
}
}
}
}
int main()
{
std::unordered_set<std::string> dictionary { "CAT", "COT", "COG", "DOT", "DOG", "BAT", "BIN", "BOG", "GOT", "HIT", "BIT" };
DictionaryGraph dictionary_graph(dictionary);
std::string start_string = "COG";
std::string end_string = "BIN";
if( dictionary.find(start_string) == dictionary.end() ||
dictionary.find(end_string) == dictionary.end() )
{
std::cout << "Bad input strings. Start:" << start_string << " End:" << end_string;
return 1;
}
Node start_node = dictionary_graph.graph.find(start_string)->second;
BreadthFirstSearch( start_node, end_string, dictionary_graph.graph );
return 0;
}
char * get_string(char *a, char *b, int pos)
{
char *d=strdup(a)
return strdup(*(d+pos)=*(b+pos));
}
void main()
{
// read the strings in a and b...
char *new_str=a;
char *buf=strdup(a);
char *tmp=a;
int cnt=0;
int n=strlen(a);
while(strcasecmp(new_str,b)!=0)
{
tmp=get_string(new_str, b, cnt%n);
if(dict_contains(tmp))
{
new_str=tmp;
// print it...
}
cnt++;
}
}
it would be helpful for us if u could give the logic behind dict_contains( ) funcion...
bool present_in_dict(char* source)
{
// have a trie.
// walk it and return true or
// false if the string is present in the trie
}
int make (char *source, char s)
{
// insert a char s into source such
// that the resulting string is in the output.
// GrEeDy :)
int i;
char ch;
for (i = 0; i < strlen(source); i++)
{
ch = source[i];
source[i] = s;
if (present_in_dict(source))
{
printf("%s",source);
return 1;
}
source[i] = ch;
}
retirn 0;
}
int Table[26];
void process (char *s)
{
for (i = 0; i < 26; i++)
{
Table[s[i]-'a']++;
}
}
void insert (char *s, char *d)
{
int i;
for (i = 0; i < 26; i++)
{
Table[i] = 0;
}
process(d);
for (i = 0; i < 26; i++)
{
if (Table[i] > 0 )
{
// if the charecter is yet to be taken
if( make (s, i + 'a') > 0 )
// 0 + a = a, 1 + a = b..
{
// this charecter got in.
Table[i]--;
// so again start from the beginning
// to see if you can insert any
// charecters.
i = 0;
}
}
}
// when all charecters are inserted this returns
}
Corrections are highly appreciated. :)
--
“A mistake is a crash-course in learning.”
--
A java method to transform.
As an interface use a small dictionary to check for the presence of the word.
Small dictionary in java
---------------------------------
HashSet<String> dictionary = new HashSet<String>();
This is used by the method
boolean isPresent(char[] input);
The transformation method in java
-------------------------------------------------
static void transform(char[] source, char[] destination){
if (source.length != destination.length)
return;
boolean bArray[] = new boolean[destination.length];
char[] transformedString = source.clone();
//The main loop
for (int count=0;count < source.length; count++){
for (int checkCount = 0; checkCount<bArray.length; checkCount++){
boolean flag = bArray[checkCount];
if(flag==true)
continue;
char[] checkTransformation = transformedString.clone();
checkTransformation[checkCount] = destination[checkCount];
if (isPresent(checkTransformation) == true){
bArray[checkCount] = true;
transformedString = checkTransformation;
break;
}
}
System.out.println(transformedString);
}
}
this is my complete solution with a test case..
class Node:
nodes = {}
def __init__(self, value=0):
self.value = value
self.nodes = {}
def add(self, n):
self.nodes[n.value] = n
def getNode(self, value):
return self.nodes.get(value)
def getValue(self):
return value
def addValue(self, str):
new = self.nodes.get(str[0])
if not new:
new = Node(str[0])
self.add(new)
if len(str) > 1:
new.addValue(str[1:])
def replace(source, dest, root):
current_word = source
current_parent = root
while (current_word != dest):
current_parent = root
for i in range(0, len(dest)):
# go through every index
# lets try to replace the ith letter
if (current_parent.getNode(dest[i])):
trial_word = current_word[0:i] + dest[i] + current_word[i+1:]
if (checkPath(current_parent.getNode(dest[i]), current_word[i+1:])):
current_word = trial_word
print (current_word)
if (current_word == dest):
break
current_parent = current_parent.getNode(current_word[i])
def checkPath(node, word):
for w in word:
node = node.getNode(w)
if not node:
return False
return True
if __name__ == '__main__':
root = Node()
words = ['dog', 'cot', 'cog', 'dot', 'dog']
for w in words:
root.addValue(w)
replace("cat", "dog", root)
From what I can tell, there is absolutely no bactracking in your code. The test example works only because your dictionary is very small. It would not work in general case. I really cannot follow your code, but it seems that if you add "hat" to your dictionary, you will get stuck with no way of recovering.
transform(String s1, String s2){
for(int i = 0; i<s1.length; i++){
if(s1[i]!=s2[i]){
s1[i]=s2[i];
}
}
}
pre-process the entire dictionary and form a graph. Now start from the first word (source node) and do Breadth first search and you will get the shortest path from the source word to the target word.
- rkt September 28, 2012