首页 > 代码库 > LeetCode OJ - Word Ladder

LeetCode OJ - Word Ladder

我觉得这道题比较难,主要是因为对于我来说:

1. 我没有把这个问题联想到树的宽度遍历(即便没有考虑树的宽度遍历,也是可以做的,但是我一开始实现的代码却是深度遍历,后来发现树的BFS一般使用queue实现的,貌似没有递归的方法??

2. 即使在意识到用BFS,却还有一个陷阱:我是对字典进行了BFS,这个说实话,代码长,还TLE;

后来参考了前辈的代码,采用对26个单词进行枚举,才解决了这个问题。

下面是AC代码:

 1 /**
 2      * Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, 
 3      * BFS && 26 characters
 4      * @param start
 5      * @param end
 6      * @param dict
 7      * @return
 8      */
 9     public int ladderLength(String start, String end, HashSet<String> dict){
10         if(start.equals(end))
11             return 2;
12         //for BFS 
13         LinkedList<String> queue = new LinkedList<String>();
14         //store the words that have visited and in the dict
15         HashSet<String> visited = new HashSet<String>();
16         //the level information for every word
17         LinkedList<Integer> level = new LinkedList<Integer>();
18         queue.offer(start);
19         level.offer(1);
20         while(!queue.isEmpty()){
21             String interW = queue.poll();
22             int le = level.poll();
23             
24             //for every character in the word
25             for(int i=0;i<interW.length();i++){
26                 
27                 char[] words = interW.toCharArray();
28                 char o = words[i];//the original word
29                 for(char c=‘a‘;c<=‘z‘;c++)
30                 {
31                     if(c!=o){
32                         //subsitude by another char
33                         words[i] = c;    
34                         String changed = new String(words);
35                         if(changed.equals(end))
36                             return le+1;
37                         if((!visited.contains(changed)) && dict.contains(changed)){
38                             visited.add(changed);
39                             queue.offer(changed);
40                             level.offer(le+1);
41                         }
42                     }
43                 }
44                 
45             }
46         }
47         return 0;
48     }