友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
127. Word Ladder
通过 Word Ladder - LeetCode 讲解，竟然可以抽象成无向无权图，然后通过 Queue 将其串联起来，实在好精巧。
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.
思路分析
BFS 解题思路，与 752. Open the Lock 的套路是一样的。
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
/**
* Runtime: 43 ms, faster than 80.36% of Java online submissions for Word Ladder.
*
* Memory Usage: 49.1 MB, less than 5.11% of Java online submissions for Word Ladder.
*
* Copy from: https://leetcode.com/problems/word-ladder/solution/[Word Ladder solution - LeetCode]
*/
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int L = beginWord.length();
Map<String, List<String>> allComboDict = new HashMap<>();
wordList.forEach(word -> {
for (int i = 0; i < L; i++) {
String newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);
List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
transformations.add(word);
allComboDict.put(newWord, transformations);
}
});
Queue<Pair<String, Integer>> Q = new LinkedList<>();
Q.add(new Pair<>(beginWord, 1));
Map<String, Boolean> visited = new HashMap<>();
visited.put(beginWord, true);
while (!Q.isEmpty()) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
Integer level = node.getValue();
for (int i = 0; i < L; i++) {
String newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);
for (String adjacentWord : allComboDict.getOrDefault(newWord, Collections.emptyList())) {
if (adjacentWord.equals(endWord)) {
return level + 1;
}
if (!visited.containsKey(adjacentWord)) {
visited.put(adjacentWord, true);
Q.add(new Pair<>(adjacentWord, level + 1));
}
}
}
}
return 0;
}
public static class Pair<K, V> {
private K key;
private V value;
public Pair(K key, V value) {
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
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
/**
* 自己解答
*/
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dic = new HashSet<>(wordList);
Set<String> seen = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
if (word.equals(endWord)) {
return step + 1;
}
if (seen.contains(word)) {
continue;
} else {
seen.add(word);
}
for (int j = 0; j < word.length(); j++) {
List<String> words = create(word, j, dic, seen);
queue.addAll(words);
}
}
step++;
}
return 0;
}
public List<String> create(String word, int index, Set<String> dic, Set<String> seen) {
List<String> result = new ArrayList<>();
char[] array = word.toCharArray();
char ec = array[index];
for (int i = 0; i < 26; i++) {
char c = (char) ('a' + i);
if (c != ec) {
array[index] = c;
String w = new String(array);
// 提前踢出掉无用单词
if (dic.contains(w) && !seen.contains(w)) {
result.add(w);
}
}
}
return result;
}