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中的每一個元素，看是不是和當(dāng)前word只相差一個字符，如果是則作為新的當(dāng)前word，直到當(dāng)前word與target只相差一個字符。實(shí)現(xiàn)代碼如下：
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 }
這個算法可以通過小數(shù)據(jù)測試，但是在大數(shù)據(jù)下報(bào)超時錯誤。主要問題是算法復(fù)雜度較高，由于dict中的單詞是亂序的，因此最壞情況下需要遍歷所有可能的轉(zhuǎn)換路徑才能做出判斷。
改變思路，其實(shí)可以通過trie樹的BFS搜索獲得結(jié)果，由于BFS是分層遍歷的，因此找到一個解之后就可以馬上返回，復(fù)雜度是O(N)，N是原單詞的長度。實(shí)現(xià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 }
其中利用了隊(duì)列對trie樹進(jìn)行BFS。