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

LeetCode OJ - Word Ladder

2024-07-02 03:11:30   225人阅读

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

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     }

 


联系
我们