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
| class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
return Collections.emptyList();
}
Map<String, Integer> wordToEdgeCountMap = new HashMap<>();
wordToEdgeCountMap.put(beginWord, 0);
Map<String, List<String>> wordToFromWordList = new HashMap<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int edgeCount = 1;
while (!queue.isEmpty()) {
for (int i = queue.size(); i > 0; i--) {
String word = queue.poll();
for (int j = 0; j < word.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) {
String nextWord = word.substring(0, j) + c + word.substring(j + 1);
if (nextWord.equals(word)) {
continue;
}
if (wordSet.contains(nextWord)) {
wordToFromWordList.computeIfAbsent(nextWord, k -> new ArrayList<>()).add(word);
if (wordToEdgeCountMap.containsKey(nextWord)) {
continue;
}
wordToEdgeCountMap.put(nextWord, edgeCount);
queue.offer(nextWord);
}
}
}
}
edgeCount++;
}
List<List<String>> resultList = new ArrayList<>();
Deque<String> sequence = new LinkedList<>();
dfs(resultList, sequence, endWord, beginWord, wordToEdgeCountMap, wordToFromWordList);
return resultList;
}
private void dfs(List<List<String>> resultList, Deque<String> sequence, String word, String beginWord, Map<String, Integer> wordToEdgeCountMap, Map<String, List<String>> wordToFromWordList) {
if (word.equals(beginWord)) {
sequence.addFirst(word);
resultList.add(new ArrayList<>(sequence));
sequence.removeFirst();
return;
}
List<String> fromWordList = wordToFromWordList.get(word);
if (fromWordList != null) {
for (String fromWord : fromWordList) {
if (wordToEdgeCountMap.get(fromWord) + 1 == wordToEdgeCountMap.get(word)) {
sequence.addFirst(word);
dfs(resultList, sequence, fromWord, beginWord, wordToEdgeCountMap, wordToFromWordList);
sequence.removeFirst();
}
}
}
}
}
|