Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
C++:
01 void GenResult(vector<vector<string>>& A, string s, map<string,
02                vector<string>>& M, vector<string>& tmp)
03 {
04     vector<string> add;
05     if(M.find(s)==M.end())
06     {
07         add.push_back(s);
08         for(int i=tmp.size()1;i>=0;i)
09         {
10             string t=tmp[i];
11             add.push_back(t);
12         }
13         A.push_back(add);
14         return;
15     }
16     vector<string> B=M[s];
17     for(int i=0;i<B.size();i++)
18     {
19         tmp.push_back(s);
20         GenResult(A,B[i],M,tmp);
21         tmp.pop_back();
22     }
23 }
24 class Solution {
25 public:
26 
27  vector<vector<string>> findLadders(string start, string end,
28                                     unordered_set<string> &dict)
29  {
30         // Start typing your C/C++ solution below
31         // DO NOT write int main() function
32         map<string, vector<string>> M;
33         unordered_set<string> K;
34         queue<string> P;
35         queue<string> Q;
36         int n=start.size();
37         P.push(start);
38         unordered_set<string>::iterator it;
39         vector<vector<string>> result;
40         dict.erase(start);
41         dict.erase(end);
42 
43         while(!P.empty())
44         {
45             string tmp=P.front();
46             P.pop();
47 
48             for(int i=0;i<n;i++)
49             {
50                 char t=tmp[i];
51                 for(char c=‘a’;c<=‘z’;c++)
52                 {
53                     if(c==t)
54                         continue;
55                     string local=tmp;
56                     local[i]=c;
57                     if((dict.find(local)!=dict.end())
58                        ||(local==end))
59                     {
60                         if(K.find(local)==K.end())
61                         {
62                             K.insert(local);
63                             Q.push(local);
64                         }
65                         M[local].push_back(tmp);
66                     }
67                 }
68             }
69             if(P.empty())
70             {
71                 if(M.find(end)!=M.end())
72                 {
73                     vector<string> W;
74                     GenResult(result,end,M,W);
75                     return result;
76                 }
77 
78                 for(it=K.begin();it!=K.end();it++)
79                 {
80                     dict.erase(*it);
81                 }
82                 K.clear();
83                 queue<string> nothing;
84                 P=Q;
85                 Q=nothing;
86             }
87         }
88         return result;
89     }
90 };
Advertisements
This entry was posted in Graph, Hashtable and Map, Stack and Queue. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s