首页 > 代码库 > [Leetcode][JAVA] Word Ladder
[Leetcode][JAVA] Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- 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.
乍看起来很难的一题，其实仔细分析就是图的遍历。把start,end和dict里的词都看作一个个结点，如果一个词可以合法转化为另一个词，那么视为这两个“结点”中间有一条路径。问题则变为，找到从start到end的最短路径长度。
如果采用扫描所有dict中单词，然后判断是否合法来遍历结点的方法，会超时（因为有dict中单词过多的用例）。所以只能采用别的遍历思路。
一个有效的遍历思路是获取到当前单词长度，然后对每一位都尝试替换为别的字符来遍历，即得到所以可能的合法字符串，然后判断是否等于end，或者在dict中且不在已遍历过的结点中，这样时间复杂度就是O(l)仅仅跟单词长度有关了。
对每一个结点，都用HashMap保存start到它的路径长度，新结点进入时只需要把长度加一即可。
采用广度优先遍历比较好，因为我们只需要获得最短的路径长度，而广度优先可以保证第一个到达end的路径是最短的（即到达end即可以return）。
代码如下：
1 public int ladderLength(String start, String end, Set<String> dict) { 2 HashMap<String, Integer> hm = new HashMap<String, Integer>(); 3 Queue<String> q = new LinkedList<String>(); 4 q.add(start); 5 hm.put(start,1); 6 7 while(!q.isEmpty()) 8 { 9 String temp = q.poll();10 int len = hm.get(temp);11 for(int i=0;i<temp.length();i++) {12 for(char c=‘a‘;c<=‘z‘;c++) {13 if(c==temp.charAt(i))14 continue;15 StringBuilder sb = new StringBuilder(temp);16 sb.setCharAt(i,c);17 String next = sb.toString();18 19 if(next.equals(end))20 return len+1;21 if(dict.contains(next) && !hm.containsKey(next)) {22 q.add(next);23 hm.put(next,len+1);24 }25 }26 }27 }28 return 0;29 }
[Leetcode][JAVA] Word Ladder