The word ladder game was invented by Lewis Carroll in 1877. The idea is to begin
ID: 3697370 • Letter: T
Question
The word ladder game was invented by Lewis Carroll in 1877. The idea is
to begin with a start word and change one letter at a time until arriving at
an end word. Each word along the way must be an English word.
For example, starting from FISH you can make a word ladder to MAST
through the following ladder:
FISH, WISH, WASH, MASH, MAST
Write a program that uses recursion to find the word ladder given a start
word and an end word, or determines if no word ladder exists. Use the
file words.txt that is available online with the source code for the book
as your dictionary of valid words. This file contains 87314 words. Your
program does not need to find the shortest word ladder between words,
any word ladder will do if one exists.
Please solve this recursively using relatively simple methods. This is a very simple program for an intro to Java course.
This has been answered before but I need original simple code. Thanks
Explanation / Answer
class Solution {
public:
vector<string> findDict(string str, unordered_set<string> &dict){
vector<string> res;
int sz = str.size();
string s = str;
for (int i=0;i<sz;i++){
s = str;
for (char j = 'a'; j<='z'; j++){
s[i]=j;
if (dict.find(s)!=dict.end()){
res.push_back(s);
}
}
}
return res;
}
bool valid(string s1,string s2){
bool flag=false;
for (int i=0;i<s1.size();i++){
if (s1[i]!=s2[i]){
if (flag==true){return false;}
else{flag=true;}
}
}
return true;
}
int ladderLength(string start, string end, unordered_set<string> &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (valid(start,end)){return 2;}
struct node{
string str;
int lev;
node(string s,int l):str(s),lev(l){}
};
queue<node>q;
queue<node>rq;
map<string,bool>mark;
map<string,bool>rmark;
for (auto it=dict.begin();it!=dict.end();it++){
mark[*it]=false;
rmark[*it]=false;
}
int level=1;
int rlevel=1;
q.push(node(start,1));
rq.push(node(end,1));
while (!q.empty() && !rq.empty()){
if (q.size()<rq.size()){
while (!q.empty() && q.front().lev==level){
vector<string> l = findDict(q.front().str,dict);
for (auto it=l.begin();it!=l.end();it++){
if (!mark[*it]){
mark[*it]=true;
if (rmark[*it]){return q.front().lev+rq.back().lev;}
q.push(node(*it,level+1));
}
}
q.pop();
}
level++;
}else{
while (!rq.empty() && rq.front().lev==rlevel){
vector<string> lr = findDict(rq.front().str,dict);
for (auto it=lr.begin();it!=lr.end();it++){
if (!rmark[*it]){
rmark[*it]=true;
if (mark[*it]){return rq.front().lev+q.back().lev;}
rq.push(node(*it,rlevel+1));
}
}
rq.pop();
}
rlevel++;
}
}
return 0;
}
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.