EEPW论坛

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 length5.

Note:

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

1. class Solution  

2. {  

3.     int ladderLength(string start, string end, unorder_set<string>& dict)  

4.     {  

5.         queue<string> q1, q2, *p1, *p2;  

6.   

7.         int count = 0;  

8.         for (p1=&q1, p2=&q2, p1->push(start); p1->size(); swap(p1, p2))  

9.         {  

10.             ++count;  

11.             for (string str; p1->size(); p1->pop())  

12.             {  

13.                 str = p1->front();  

14.                 for (int i=0; i<str.length(); i++)  

15.                 {  

16.                     string s = str;  

17.                     for (char ch = 'a'; ch <= 'z'; ++ch)  

18.                     {  

19.                         if (ch==str[i])  

20.                         {  

21.                             continue;  

22.                         }  

23.                         s[i] = ch;  

24.                         if (s==end)  

25.                         {  

26.                             return count + 1;  

27.                         }  

28.   

29.                         if (dict.find(s)!=dict.end())  

30.                         {  

31.                             p2->push(s);  

32.                             dict.erase(s);  

33.                         }  

34.                     }  

35.                 }  

36.             }  

37.         }  

38.         return 0;  

39.     }  

40. };