Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
C++:
01 class Solution {
02 public:
03     int ladderLength(string start, string end,
04                      unordered_set<string> &dict) {
05         // Start typing your C/C++ solution below
06         // DO NOT write int main() function
07         int n=start.size();
08         if(n==1)
09             return 2;
10         int result=2;
11         queue<string> P;
12         queue<string> Q;
13         P.push(start);
14         while(!P.empty())
15         {
16             string tmp=P.front();
17             P.pop();
18             for(int i=0;i<n;i++)
19             {
20                 char t=tmp[i];
21                 for(char a=‘a’;a<=‘z’;a++)
22                 {
23                     if(t==a)
24                     {
25                         continue;
26                     }
27                     tmp[i]=a;
28                     if(tmp==end)
29                     {
30                         return result;
31                     }
32                     if(dict.find(tmp)!=dict.end())
33                     {
34                         Q.push(tmp);
35                         dict.erase(tmp);
36                     }
37                 }
38                 tmp[i]=t;
39             }
40             if(P.empty())
41             {
42                 queue<string> T=P;
43                 P=Q;
44                 Q=T;
45                 result++;
46             }
47         }
48         return 0;
49     }
50 };
Advertisements
This entry was posted in Graph, Stack and Queue, String. 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