Find a way that each intermediate word exist in a given dictionary -- Ebay

Solution

// FindPath.cpp : Defines the entry point for the console application.

//

#include <iostream>

#include <string>

#include <list>

#include <vector>

#include <set>

#include <iterator>

#include <stack>

using namespace std;

int Distance(string& str1, string& str2)

{

if(str1.length() != str2.length()){

return 10000;

}

int dist = 0;

for(int i = 0; i < str1.length(); ++i){

if(tolower(str1[i]) != tolower(str2[i])){

dist ++;

}

}

return dist;

}

bool FindString(stack<string>& s, string str)

{

bool found = false;

stack<string> s1;

string temp;

while(!s.empty()){

temp = s.top();

if(temp == str){

found = true;

}

s1.push(temp);

s.pop();

if(found){

break;

}

}

while(!s1.empty()){

temp = s1.top();

s.push(temp);

s1.pop();

}

return found;

}

void FindPath(

set<string>& dict,

set<string>& visited,

stack<string>& visiting,

string& target,

vector<string> &path)

{

if(visiting.empty()){

cout << "Cannot found a path" << endl;

return;

}

string start = visiting.top();

visiting.pop();

if(Distance(start, target) == 1){

cout << "Find a path " << endl;

copy(path.begin(), path.end(), ostream_iterator<string>(cout, " "));

cout << start << " " << target << endl;

return;

}

bool addOne = false;

for(set<string>::iterator it = dict.begin(); it != dict.end(); ++it){

if(Distance((string)*it, start) == 1 && !FindString(visiting, *it) && (visited.find(*it) == visited.end() || visited.empty())){

visiting.push(*it);

addOne = true;

}

}

visited.insert(start);

if(addOne){

path.push_back(start);

}

FindPath(dict, visited, visiting, target, path);

if(!path.empty()){

path.pop_back();

}

}

void InitDict(set<string>& dict)

{

dict.insert("pit");

dict.insert("can");

dict.insert("pot");

dict.insert("pet");

dict.insert("mop");

dict.insert("mat");

dict.insert("met");

dict.insert("map");

dict.insert("end");

dict.insert("bye");

dict.insert("cot");

dict.insert("vet");

dict.insert("hello");

dict.insert("world");

dict.insert("chop");

dict.insert("look");

dict.insert("seek");

dict.insert("book");

dict.insert("Jack");

dict.insert("Jeep");

dict.insert("soft");

dict.insert("hard");

dict.insert("hear");

dict.insert("hare");

dict.insert("lamp");

dict.insert("week");

dict.insert("work");

dict.insert("shot");

dict.insert("stop");

dict.insert("shop");

dict.insert("ship");

dict.insert("chip");

dict.insert("chop");

dict.insert("chap");

dict.insert("clap");

dict.insert("clay");

}

int main(int argc, char* argv[])

{

set<string> dict;

InitDict(dict);

typedef struct

{

string first;

string second;

} Pair;

Pair testCases[] = {

{"pit", "map"},

{"bye", "cot"},

{"shot", "clay"}};

for(int i = 0; i < sizeof(testCases)/ sizeof(Pair); ++i){

cout << "Find a path between " << testCases[i].first << " and " << testCases[i].second << endl;

stack<string> visiting;

visiting.push(testCases[i].first);

set<string> visited;

string target = testCases[i].second;

vector<string> path;

FindPath(dict, visited, visiting, target, path);

cout << endl;

}

return 0;

}

Output

Find a path between pit and map

Find a path

pit pot pet met mat map

Find a path between bye and cot

Cannot found a path

Find a path between shot and clay

Find a path

shot shop ship chip chap clap clay

Press any key to continue . . .