LeetCode(62) -- 126

P126. Word Ladder II (Hard)

给两个单词，一个是起始单词，另一个是终点单词。还给一个单词列表。从起始单词开始，每次只能修改其中的一个字母，并且修改的单词必须在列表中。如果通过数次修改，就能改成终点单词，就把这条修改路径返回。必须返回所有的路径。

我的思路

想了好久才意识到这是一个“图”的题，有起始点和终点，要找出中间所有可能的路径。

最优解

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        if (wordList == null || wordList.size() == 0) {
            return result;
        }
        Set<String> dicts = new HashSet<>(wordList);
        if (!dicts.contains(endWord)) {
            return result;
        }
        Set<String> start = new HashSet<>();
        Set<String> end = new HashSet<>();
        Map<String, List<String>> map = new HashMap<>();
        start.add(beginWord);
        end.add(endWord);
        bfs(map, start, end, dicts, false);
        List<String> subList = new ArrayList<>();
        subList.add(beginWord);
        dfs(map, result, subList, beginWord, endWord);
        return result;
    }

    private void bfs(Map<String, List<String>> map, Set<String> start,
                     Set<String> end, Set<String> dicts, boolean reverse) {
        // Processed all the word in start
        if (start.isEmpty() || end.isEmpty()) {
            return;
        }
        dicts.removeAll(start);
        Set<String> nextSet = new HashSet<>();
        boolean finish = false;
        for (String str : start) {
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char old = chars[i];
                for (char n = 'a' ; n <='z'; n++) {
                    chars[i] = n;
                    String candidate = new String(chars);
                    if (!dicts.contains(candidate)) {
                        continue;
                    }
                    if (end.contains(candidate)) {
                        finish = true;
                    } else {
                        nextSet.add(candidate);
                    }
                    String key = reverse ? candidate : str;
                    String value = reverse ? str : candidate;
                    if (! map.containsKey(key)) {
                        map.put(key, new ArrayList<>());
                    }
                    map.get(key).add(value);
                }
                // restore after processing
                chars[i] = old;
            }
        }
        if (!finish) {
            if (nextSet.size() > end.size()) {
                bfs(map, end, nextSet, dicts, !reverse);
            } else {
                bfs(map, nextSet, end, dicts, reverse);
            }
        }
    }

    private void dfs (Map<String, List<String>> map,
                      List<List<String>> result , List<String> subList,
                      String beginWord, String endWord) {
        if(beginWord.equals(endWord)) {
            result.add(new ArrayList<>(subList));
            return;
        }
        if (!map.containsKey(beginWord)) {
            return;
        }
        for (String word : map.get(beginWord)) {
            subList.add(word);
            dfs(map, result, subList, word, endWord);
            subList.remove(subList.size() - 1);
        }
    }
}