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
|
class {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>();
if (beginWord == null || endWord == null || beginWord.length() != endWord.length() ||
wordList == null || wordList.size() == 0) {
return result;
}
Map<String, List<String>> graph = new HashMap<>();
Map<String, Integer> dMap = new HashMap<>();
Set<String> wordSet = new HashSet<>(wordList);
wordSet.add(beginWord);
if (!wordSet.contains(endWord)) {
return result;
}
bfs(beginWord, endWord, wordSet, dMap, graph);
dfs(beginWord, endWord, dMap, graph, result, new ArrayList<>());
return result;
}
private void bfs(String beginWord, String endWord, Set<String> wordSet, Map<String, Integer> dMap, Map<String, List<String>> graph) {
Queue<String> q = new LinkedList<>();
q.offer(endWord);
dMap.put(endWord, 0);
int paces = 0;
for (String s : wordSet) {
graph.put(s, new ArrayList<String>());
}
while(!q.isEmpty()) {
paces++;
int size = q.size();
for (int i = 0; i < size; i++) {
String w = q.poll();
List<String> nextWords = nextWords(w, wordSet);
graph.get(w).addAll(nextWords);
for (String next : nextWords) {
if (!dMap.containsKey(next)) {
q.offer(next);
dMap.put(next, paces);
}
}
}
}
}
private List<String> nextWords(String word, Set<String> wordSet) {
List<String> result = new ArrayList<>();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char cur = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == cur) {
continue;
}
chars[i] = c;
String newString = new String(chars);
if (wordSet.contains(newString)) {
result.add(newString);
}
}
chars[i] = cur;
}
return result;
}
private void dfs(String currentWord, String endWord, Map<String, Integer> dMap, Map<String, List<String>> graph,
List<List<String>> result, List<String> path) {
path.add(currentWord);
if (currentWord.equals(endWord)) {
result.add(new ArrayList<>(path));
} else {
for (String s : graph.get(currentWord)) {
if (dMap.get(currentWord) == dMap.get(s) + 1) {
dfs(s, endWord, dMap, graph, result, path);
}
}
}
path.remove(path.size() - 1);
}
}
|
近期评论