Posted Updated Leetcode8 minutes read (About 1163 words)0 visits

Word Ladder类型题

Word Ladder I和Word Ladder II两道题给我们的经验：

  1. It’s much faster than one-end search indeed as explained in wiki.
  2. BFS isn’t equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
  3. It’s safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
  4. It seems like if(set.add()) is a little slower than if(!contains()) then add() but it’s more concise.
  1. Word Ladder
    最简单的单向BFS使用Queue来做的解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
127. Word Ladder
Medium

1980

932

Favorite

Share
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
*/
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if(!set.contains(endWord)){
            return 0;
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int count = 1;
        
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size!=0){
                String temp = queue.poll();
                if(temp.equals(endWord)){
                    return count;
                }
                for(int i = 0;i<=temp.length()-1;i++){
                    for(char c = 'a';c<='z';c++){
                        if(temp.charAt(i)!=c){
                            String newString = temp.substring(0, i)+c+temp.substring(i+1);
                            if(set.contains(newString)){
                                queue.offer(newString);
                                set.remove(newString);//避免出现环在图中
                            }
                        }
                    }
                }
                
                size--;
            }
            
            count++;

        }
        return 0;
    }
}

使用HashSet来作为Queue的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if(!wordList.contains(endWord)){
            return 0;
        }
        Set<String> queue = new HashSet<>();
        queue.add(beginWord);
        int count = 1;
        while(queue.size()!=0){
            Set<String> temp = new HashSet<>();
            for(String word:queue){
                if(word.equals(endWord)){
                    return count;
                }
                for(int i =0;i<=word.length()-1;i++){
                    for(char c = 'a';c<='z';c++){
                        if(word.charAt(i)==c)
                            continue;
                        String newString = word.substring(0, i)+c+word.substring(i+1);
                        if(set.contains(newString)){
                            temp.add(newString);
                            set.remove(newString);
                        }
                    }
                }
            }
            count++;
            queue = temp;
        }
        
        return 0;
        
    }
}

进一步提升使用双向BFS来做，双向BFS使用Queue来做BFS就很麻烦了，这个时候使用HashSet就很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if(!set.contains(endWord)){
            return 0;
        }
        Set<String> forwardSet = new HashSet<>();
        forwardSet.add(beginWord);
        Set<String> backwardSet = new HashSet<>();
        backwardSet.add(endWord);
        
        int count = 1;
        while(!(forwardSet.isEmpty() ||backwardSet.isEmpty())){
            if(backwardSet.size()<forwardSet.size()){
                Set<String> temp = new HashSet<>();
                temp = backwardSet;
                backwardSet = forwardSet;
                forwardSet = temp;
            }
            
            Set<String> tmp = new HashSet<>();

            for(String word:forwardSet){
                if(backwardSet.contains(word)){
                    return count;
                }
                for(int i = 0;i<=word.length()-1;i++){
                    for(char c='a';c<='z';c++){
                        if(word.charAt(i)==c)
                            continue;
                        String newString = word.substring(0, i)+c+word.substring(i+1);
                        if(set.contains(newString)){
                            tmp.add(newString); 
                            //和单向不同，这里不用remove from set
                        }
                       
                    }
                }
            }
            count++;
            forwardSet = tmp;
            
        }
        
        return 0;
        
        
    }
}
  1. Word Ladder II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*
126. Word Ladder II
Hard

1276

216

Favorite

Share
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:

Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
*/

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Map<String, List<String>> graph = buildGraph(beginWord, endWord, wordList);
        List<List<String>> ans = new LinkedList<>();
        System.out.println(graph);
        List<String> l = new LinkedList<>();
        dfs(graph, beginWord, endWord, ans, l);
        return ans;
    }
    
    private void dfs(Map<String, List<String>> graph, String word, String endWord, List<List<String>> ans, List<String> l){
        if(word.equals(endWord)){
            l.add(word);
            ans.add(new LinkedList<>(l));
            l.remove(l.size()-1);
            return;
        }
        if(!graph.containsKey(word)){
            return;
        }
        List<String> tmp = graph.get(word);
        l.add(word);
        for(String t:tmp){
            dfs(graph, t, endWord, ans, l);
        }
        l.remove(l.size()-1);
        
    }
    
    private Map<String, List<String>> buildGraph(String beginWord, String endWord, List<String> wordList){
        Set<String> set = new HashSet<>(wordList);
        Map<String, List<String>> graph = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        set.remove(beginWord);
        boolean finished = false;
        
        while(!queue.isEmpty() && finished==false){
            int size = queue.size();
            Set<String> visited = new HashSet<>();//这里是这道题构造图的关键地方，因为我们不想要出现过的点再次出现的图里面，但是又不能直接删除遇到的newWord，因为在同一层可能两个词的child都是这个newWord，如果直接删除会造成少一条路径，所以我们先把它们放入一个set，等着一层遍历完再一起删掉
            while(size>0){
                String word = queue.poll();

                
                for(int i =0;i<=word.length()-1;i++){
                    for(char c = 'a';c<='z';c++){
                        if(c==word.charAt(i))
                            continue;
                        String newWord = word.substring(0, i) + c + word.substring(i+1);
                        if(newWord.equals(endWord)){
                            finished = true;
                        }
                        List<String> neighbors = new LinkedList<>();
                        if(graph.containsKey(word)){
                            neighbors = graph.get(word);
                        }
                       if(set.contains(newWord)){
                            neighbors.add(newWord);
                            graph.put(word, neighbors);
                       }               
                       if(set.contains(newWord)&&!visited.contains(newWord)){//这个条件也要格外注意，必须是set有且visited没有的才加入到graph中
                            queue.offer(newWord);
                        }
                        visited.add(newWord);
                    }
                }
                size--;
            }
            set.removeAll(visited);
        }
        return graph;
    }
}
Follow
×