LeetCode - Word Ladder
Problem description
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:
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:
1
2
3
4
5
6
7
8
9
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:
1
2
3
4
5
6
7
8
9
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.
Analysis
The general idea is to use BFS.
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
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int res = 0;
int len = beginWord.length();
int size = wordList.size();
HashMap<String, List<String>> map = new HashMap<>();
getNeighbors(wordList, map, beginWord);
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
boolean[] visited = new boolean[size];
HashMap<String, Integer> indexes = new HashMap<>();
for (int i = 0; i < size; i++){
indexes.put(wordList.get(i), i);
}
if (indexes.containsKey(beginWord)){
visited[indexes.get(beginWord)] = true;
}
while (!q.isEmpty()){
int siz = q.size();
res++;
if (res > size + 1){
return 0;
}
for (int i = 0; i < siz; i++){
String str = q.poll();
if (!str.equals(beginWord)){
int index = indexes.getOrDefault(str, -1);
if (index == -1 || visited[index]){
continue;
}
visited[index] = true;
}
if (str.equals(endWord)){
return res;
}
for(String s:map.getOrDefault(str, new ArrayList<>())){
q.offer(s);
}
}
}
return 0;
}
void getNeighbors(List<String> list, HashMap<String, List<String>> map, String start){
HashSet<String> set = new HashSet<>();
for (String s: list){
set.add(s);
}
int len = start.length();
for (int i = 0; i< len; i++){
char old = start.charAt(i);
for (int j = 0; j< 26; j++){
char newChar = (char)('a' + j);
if (newChar == old){
continue;
}
String newString = start.substring(0,i) + newChar + start.substring(i+1);
if (set.contains(newString)){
List<String> li = map.getOrDefault(start, new ArrayList<>());
li.add(newString);
map.put(start, li);
}
}
}
for (String s:list){
for (int i = 0; i< len; i++){
char old = s.charAt(i);
for (int j = 0; j< 26; j++){
char newChar = (char)('a' + j);
if (newChar == old){
continue;
}
String newString = s.substring(0,i) + newChar + s.substring(i+1);
if (!newString.equals(s) && set.contains(newString)){
List<String> li = map.getOrDefault(s, new ArrayList<>());
li.add(newString);
map.put(s, li);
}
}
}
}
}
}
Another method to improve performance is to use bidirectional BFS.
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> visited = new HashSet<>();
Set<String> start = new HashSet<>();
Set<String> end = new HashSet<>();
start.add(beginWord);
end.add(endWord);
int step = 1;
while(!start.isEmpty() && !end.isEmpty()) {
if(start.size() > end.size()){
Set<String> temp = start;
start = end;
end = temp;
}
Set<String> next = new HashSet<>();
for(String word : start) {
char[] chars = word.toCharArray();
for(int j = 0; j < word.length(); j++) {
char old = chars[j];
for(char c = 'a'; c <='z'; c++) {
chars[j] = c;
String nextWord = new String(chars);
if(end.contains(nextWord)) {
return step + 1;
}
if(set.contains(nextWord) && !visited.contains(nextWord)) {
next.add(nextWord);
visited.add(nextWord);
}
}
chars[j] = old;
}
}
start = next;
step++;
}
return 0;
}
}
What to improve
- if we know both start and end, and it doesn’t matter if we from start to end or from end to start, we can use BFS from start and end, and we expand the smaller one so that it can be faster.