LeetCode link
first thought
the same as word ladder problem, just need to record paths to the current word
solution
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
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Map<String, List<List<String>>> map = new HashMap<>();
for (String word: wordList) {
map.put(word, new ArrayList<List<String>>());
}
List<List<String>> beginList = new ArrayList<>();
List<String> begin = new ArrayList<>();
begin.add(beginWord);
beginList.add(begin);
map.put(beginWord, beginList);
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
while (!queue.isEmpty()) {
String word = queue.poll();
ArrayList list = (ArrayList)map.get(word);
char[] chars = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
char originalChar = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == originalChar) {
continue;
}
chars[i] = c;
String newStr = new String(chars);
if (map.containsKey(newStr)) {
ArrayList newStrList = (ArrayList)map.get(newStr);
if (this.isNeedUpdate(newStrList, list)) {
newStrList.clear();
for (int j = 0; j < list.size(); j++) {
ArrayList<String> tempList = (ArrayList)(list.get(j));
List<String> newList = new ArrayList(tempList);
newList.add(newStr);
newStrList.add(newList);
}
map.put(newStr, newStrList);
if (!newStr.equals(endWord)) {
queue.add(newStr);
}
}
}
}
chars[i] = originalChar;
}
}
return map.get(endWord) == null ? new ArrayList<>() : map.get(endWord);
}
private boolean isNeedUpdate(ArrayList<ArrayList<String>> newStrList, ArrayList<ArrayList<String>> list) {
if (newStrList.size() < 1) {
return true;
}
ArrayList newStrList0 = newStrList.get(0);
ArrayList list0 = list.get(0);
if (newStrList0.size() > list0.size() + 1 || (newStrList0.size() == list0.size() + 1 && newStrList.size() < list.size())) {
return true;
}
return false;
}
}
problem
Your input
Your answer
Expected answer
reason
it seems missing answers, maybe during the update part.
modification
when the path size is equal, should not to clear all the list, if not so, it would clear the previous valid paths.
change the outer list to set, to make sure there’s no duplicate in iterating.
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
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Map<String, Set<List<String>>> map = new HashMap<>();
Map<String, Integer> distance = new HashMap<>();
for (String word: wordList) {
map.put(word, new HashSet<List<String>>());
distance.put(word, Integer.MAX_VALUE);
}
Set<List<String>> beginList = new HashSet<>();
List<String> begin = new ArrayList<>();
begin.add(beginWord);
beginList.add(begin);
map.put(beginWord, beginList);
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
distance.put(beginWord, 1);
while (!queue.isEmpty()) {
String word = queue.poll();
HashSet list = (HashSet)map.get(word);
char[] chars = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
char originalChar = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == originalChar) {
continue;
}
chars[i] = c;
String newStr = new String(chars);
if (map.containsKey(newStr)) {
HashSet newStrList = (HashSet)map.get(newStr);
boolean isNeedUpdate = false;
if (newStrList.size() < 1) {
isNeedUpdate = true;
newStrList.clear();
} else {
if (distance.get(newStr) > distance.get(word) + 1) {
isNeedUpdate = true;
newStrList.clear();
} else if (distance.get(newStr) == distance.get(word) + 1 && newStrList.size() < list.size()) {
isNeedUpdate = true;
}
}
if (isNeedUpdate) {
Iterator iter = list.iterator();
while (iter.hasNext()) {
ArrayList tempList = (ArrayList)iter.next();
List<String> newList = new ArrayList(tempList);
newList.add(newStr);
newStrList.add(newList);
}
map.put(newStr, newStrList);
if (!newStr.equals(endWord)) {
queue.add(newStr);
}
}
}
}
chars[i] = originalChar;
}
}
if (map.get(endWord) == null) {
return new ArrayList<>();
}
ArrayList<List<String>> result = new ArrayList<>();
Iterator iter = ((HashSet)map.get(endWord)).iterator();
while (iter.hasNext()) {
ArrayList list = (ArrayList)iter.next();
result.add(list);
}
return result;
}
}
problem
Surely TLE…
reason
full of sets…
modification
have seen the answer, the main idea of this problem is maintain a map of each word’s prewordlist, and using dfs to recursive the paths to the end.
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
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>();
Set<String> wordSet = new HashSet<>();
for (String word: wordList) {
wordSet.add(word);
}
Map<String, List<String>> preWords = new HashMap<>();
Queue<String> queue = new LinkedList<>();
boolean hasFound = false;
queue.add(beginWord);
wordSet.remove(beginWord);
while (!queue.isEmpty() && wordSet.size() > 0) {
Queue<String> queue2 = new LinkedList<>();
while (!queue.isEmpty() && wordSet.size() > 0) {
String str = queue.poll();
List<String> validWords = this.validWords(str, wordSet);
for (String newStr: validWords) {
List<String> list = new ArrayList<>();
if (preWords.containsKey(newStr)) {
list = preWords.get(newStr);
}
list.add(str);
preWords.put(newStr, list);
if (newStr.equals(endWord)) {
hasFound = true;
}
if (!hasFound) {
queue2.add(newStr);
}
}
}
if (!hasFound) {
queue = queue2;
}
}
List<String> path = new ArrayList<>();
path.add(endWord);
this.dfs(preWords, endWord, path, result);
return result;
}
private List<String> validWords(String str, Set<String> wordSet) {
List<String> words = new ArrayList<>();
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c != original) {
chars[i] = c;
String newStr = new String(chars);
if (wordSet.contains(newStr)) {
wordSet.remove(newStr);
words.add(newStr);
}
}
}
chars[i] = original;
}
return words;
}
private void dfs(Map<String, List<String>> map, String word, List<String> path, List<List<String>> result) {
if (!map.containsKey(word)) {
if (path.size() > 1) {
List<String> newPath = new ArrayList<>(path);
Collections.reverse(newPath);
result.add(newPath);
return;
}
}
List<String> pre = map.get(word);
for (String s: pre) {
path.add(s);
this.dfs(map, s, path, result);
path.remove(path.size() - 1);
}
}
}
problem
wrong answer, missing answers
reason
the timing of delete the wordSet is not proper.
modification
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
while (!queue.isEmpty() && wordSet.size() > 0) {
Queue<String> queue2 = new LinkedList<>();
List<String> temp = new ArrayList<>();
while (!queue.isEmpty() && wordSet.size() > 0) {
String str = queue.poll();
List<String> validWords = this.validWords(str, wordSet);
temp.addAll(validWords);
for (String newStr: validWords) {
List<String> list = new ArrayList<>();
if (preWords.containsKey(newStr)) {
list = preWords.get(newStr);
}
list.add(str);
preWords.put(newStr, list);
if (newStr.equals(endWord)) {
hasFound = true;
}
if (!hasFound) {
queue2.add(newStr);
}
}
}
wordSet.removeAll(temp);
if (!hasFound) {
queue = queue2;
}
}
problem
duplicated answers…
Input:
reason
still the timing.
not the timing, it because queue2 may contain duplicated strings. some words in one layer may produce the same word, so the word be added to queue2 for several times.
modification
change queue2 to a set.
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
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>();
Set<String> wordSet = new HashSet<>();
for (String word: wordList) {
wordSet.add(word);
}
Map<String, List<String>> preWords = new HashMap<>();
Queue<String> queue = new LinkedList<>();
boolean hasFound = false;
queue.add(beginWord);
wordSet.remove(beginWord);
while (!queue.isEmpty() && wordSet.size() > 0) {
Set<String> queue2 = new HashSet<>();
while (!queue.isEmpty() && wordSet.size() > 0) {
String str = queue.poll();
List<String> validWords = this.validWords(str, wordSet);
for (String newStr: validWords) {
if (!preWords.containsKey(newStr)) {
preWords.put(newStr, new ArrayList<String>());
}
preWords.get(newStr).add(str);
if (newStr.equals(endWord)) {
hasFound = true;
}
queue2.add(newStr);
}
}
wordSet.removeAll(queue2);
if (!hasFound) {
queue.addAll(queue2);
}
}
List<String> path = new ArrayList<>();
path.add(endWord);
this.dfs(preWords, endWord, path, result);
return result;
}
private List<String> validWords(String str, Set<String> wordSet) {
List<String> words = new ArrayList<>();
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c != original) {
chars[i] = c;
String newStr = new String(chars);
if (wordSet.contains(newStr)) {
words.add(newStr);
}
}
}
chars[i] = original;
}
return words;
}
private void dfs(Map<String, List<String>> map, String word, List<String> path, List<List<String>> result) {
if (!map.containsKey(word)) {
if (path.size() > 1) {
List<String> newPath = new ArrayList<>(path);
Collections.reverse(newPath);
result.add(newPath);
}
return;
}
List<String> pre = map.get(word);
for (String s: pre) {
path.add(s);
this.dfs(map, s, path, result);
path.remove(path.size() - 1);
}
}
}
近期评论