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
wrong answer

Your input
“hit”
“cog”
[“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Your answer
[[“hit”,”hot”,”dot”,”dog”,”cog”]]

Expected answer
[[“hit”,”hot”,”lot”,”log”,”cog”],[“hit”,”hot”,”dot”,”dog”,”cog”]]

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:
“red”
“tax”
[“ted”,”tex”,”red”,”tax”,”tad”,”den”,”rex”,”pee”]
Output:
[[“red”,”ted”,”tad”,”tax”],[“red”,”ted”,”tex”,”tax”],[“red”,”rex”,”tex”,”tax”],[“red”,”ted”,”tex”,”tax”],[“red”,”rex”,”tex”,”tax”]]
Expected:
[[“red”,”ted”,”tad”,”tax”],[“red”,”ted”,”tex”,”tax”],[“red”,”rex”,”tex”,”tax”]]

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);
        }
    }
}