127 Word Ladder

Search…
127 Word Ladder
127. Word Ladder
1. Question
Given two words (beginWordandendWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWordtoendWord, such that:
1.Only one letter can be changed at a time
2.Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord="hit"
endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]
Return
1
  [
2
    ["hit","hot","dot","dog","cog"],
3
    ["hit","hot","lot","log","cog"]
4
  ]
Copied!
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.
2. Implementation
(1) BFS
1
class Solution {
2
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
3
        if (wordList.size() == 0) {
4
            return 0;
5
        }
6
​
7
        Set<String> dict = new HashSet<>();
8
​
9
        for (String word : wordList) {
10
            dict.add(word);
11
        }
12
​
13
        Queue<String> queue = new LinkedList<>();
14
        queue.add(beginWord);
15
​
16
        Set<String> visited = new HashSet<>();
17
        visited.add(beginWord);
18
​
19
        int len = 1;
20
​
21
        while (!queue.isEmpty()) {
22
            int size = queue.size();
23
​
24
            for (int i = 0; i < size; i++) {
25
                String curWord = queue.remove();
26
​
27
                if (curWord.equals(endWord)) {
28
                    return len;
29
                }
30
​
31
                char[] letters = curWord.toCharArray();
32
                for (int j = 0; j < curWord.length(); j++) {
33
                    char oldC = letters[j];
34
                    for (char c = 'a'; c <= 'z'; c++) {
35
                        letters[j] = c;
36
​
37
                        String nextWord = new String(letters);
38
​
39
                        if (dict.contains(nextWord) && !visited.contains(nextWord)) {
40
                            visited.add(nextWord);
41
                            queue.add(nextWord);
42
                            dict.remove(nextWord);
43
                        }
44
                    }
45
                    letters[j] = oldC;
46
                }
47
            }
48
            ++len;
49
        }
50
        return 0;
51
    }
52
}
Copied!
(2) Bi-directional BFS
1
class Solution {
2
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
3
        if (wordList.size() == 0) {
4
            return 0;
5
        }
6
​
7
        Set<String> dict = new HashSet<>();
8
​
9
        for (String word : wordList) {
10
            dict.add(word);
11
        }
12
​
13
        if (!dict.contains(endWord)) {
14
            return 0;
15
        }
16
​
17
        Set<String> visited = new HashSet<>();
18
        Set<String> begin = new HashSet<>();
19
        Set<String> end = new HashSet<>();
20
​
21
        begin.add(beginWord);
22
        end.add(endWord);
23
​
24
        int len = 1;
25
​
26
        while (!begin.isEmpty() && !end.isEmpty()) {
27
            if (begin.size() > end.size()) {
28
                Set<String> set = begin;
29
                begin = end;
30
                end = set;
31
            }
32
​
33
            Set<String> temp = new HashSet<>();
34
​
35
            for (String word : begin) {                
36
                char[] letters = word.toCharArray();
37
​
38
                for (int i = 0; i < letters.length; i++) {
39
                    char oldC = letters[i];
40
​
41
                    for (char c = 'a'; c <= 'z'; c++) {
42
                        letters[i] = c;
43
​
44
                        String nextWord = new String(letters);
45
​
46
                        if (end.contains(nextWord)) {
47
                            return len + 1;
48
                        }
49
​
50
​
51
                        if (dict.contains(nextWord) && !visited.contains(nextWord)) {
52
                            visited.add(nextWord);
53
                            temp.add(nextWord);
54
                        }
55
                    }
56
                    letters[i] = oldC;
57
                }
58
            }
59
            ++len;
60
            begin = temp;
61
        }
62
        return 0;
63
    }
64
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度:O(n * L * 26),其中n为word的个数，L为每个word的平均长度， 空间复杂度: O(n)
126 Word Ladder II
130 Surrounded Regions
Last modified 2yr ago
Copy link
Contents
127. Word Ladder
1. Question
2. Implementation
3. Time & Space Complexity