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:
1. Return 0 if there is no such transformation sequence.
2. All words have the same length.
3. All words contain only lowercase alphabetic characters.
第一个思路是遍历dict中的每一个元素，看是不是和当前word只相差一个字符，如果是则作为新的当前word，直到当前word与target只相差一个字符。实现代码如下：
1 public class Solution {
2 public int ladderLength(String start, String end, HashSet<String> dict) {
3 HashSet<String> trash = new HashSet<String>();
4 return searchWordLadder(start, end, dict, trash) + 1;
5 }
6
7 private int searchWordLadder(String start, String end, HashSet<String> dict, HashSet<String> trash) {
8 if (stringDiff(start, end) == 1) return 1;
9 if (dict.size() == trash.size()) return 0;
10 int steps = Integer.MAX_VALUE;
11 for (String word : dict) {
12 if (!trash.contains(word) && stringDiff(start, word) == 1) {
13 trash.add(word);
14 int lt = searchWordLadder(word, end, dict, trash);
15 if (lt != 0 && lt < steps) {
16 steps = lt;
17 }
18 trash.remove(word);
19 }
20 }
21 return steps == Integer.MAX_VALUE ? 0 : steps + 1;
22 }
23
24 private int stringDiff(String s1, String s2) {
25 int diff = 0;
26 int length = s1.length();
27 for (int i = 0; i < length; i++) {
28 if (s1.charAt(i) != s2.charAt(i)) {
29 diff++;
30 }
31 }
32 return diff;
33 }
34 }
这个算法可以通过小数据测试，但是在大数据下报超时错误。主要问题是算法复杂度较高，由于dict中的单词是乱序的，因此最坏情况下需要遍历所有可能的转换路径才能做出判断。
改变思路，其实可以通过trie树的BFS搜索获得结果，由于BFS是分层遍历的，因此找到一个解之后就可以马上返回，复杂度是O(N)，N是原单词的长度。实现代码如下：
1 public class WordLadder {
2 public int ladderLength(String start, String end, HashSet<String> dict) {
3 if (dict.size() == 0)
4 return 0;
5 int currentLevel = 1;
6 int nextLevel = 0;
7 int step = 1;
8 boolean found = false;
9 Queue<String> st = new LinkedList<String>();
10 HashSet<String> visited = new HashSet<String>();
11 st.add(start);
12 while (!st.isEmpty()) {
13 String s = st.remove();
14 currentLevel--;
15 if (stringDiff(s, end) == 1) {
16 found = true;
17 step++;
18 break;
19 } else {
20 int length = s.length();
21 StringBuffer sb = new StringBuffer(s);
22 for (int i = 0; i < length; i++) {
23 for (int j = 0; j < 26; j++) {
24 char c = sb.charAt(i);
25 sb.setCharAt(i, (char) ('a' + j));
26 if (dict.contains(sb.toString())
27 && !visited.contains(sb.toString())) {
28 nextLevel++;
29 st.add(sb.toString());
30 visited.add(sb.toString());
31 }
32 sb.setCharAt(i, c);
33 }
34 }
35 }
36 if (currentLevel == 0) {
37 currentLevel = nextLevel;
38 nextLevel = 0;
39 step++;
40 }
41 }
42 return found ? step : 0;
43 }
44
45 private int stringDiff(String s1, String s2) {
46 int diff = 0;
47 int length = s1.length();
48 for (int i = 0; i < length; i++) {
49 if (s1.charAt(i) != s2.charAt(i)) {
50 diff++;
51 }
52 }
53 return diff;
54 }
55 }
其中利用了队列对trie树进行BFS。