127. Word Ladder

著名高频题，在lc还不到200题的时代算是难题了，时间复杂度爆炸的典范，也是BFS经典题目。

我们要确保 “路线最短”，所以要用 BFS 解决，两层字典首次相交的地方一定是最短路线。

三点注意：

int size = queue.size();
    for (int i = 0; i < size; ++i){ ...

1. 这一步，上次也犯错了，查了好久才查出来，因为我直接把下一层的元素插到queue后面了，这是queue这种结构的优势，省了一步，但同时大小也在发生变化，所以必须先把当前层的大小确定了，才能BFS逐层遍历嘛。

2. 另外注意不要用ArrayList的contains方法，使用HashSet的contains方法代替。还是有区别的。

3. 最后，我发现把替换char的步骤抽取成一个方法，会比substring拼接快100+ ms。

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>();
        for (String word : wordList) {
            dict.add(word);
        }

        if (beginWord.equals(endWord)) return 1;

        Set<String> set = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        set.add(beginWord);

        int count = 1;
        while (!queue.isEmpty()) {
            count++;
            int size = queue.size();
            for (int i = 0; i < size; ++i){
                String tmp = queue.poll();
                for (String s : bfs(tmp, dict)) {
                    if (set.contains(s)) continue;
                    if (s.equals(endWord)) return count;
                    set.add(s);
                    queue.offer(s);
                }
            }
        }
        return 0;
    }
    private List<String> bfs(String word, Set<String> dict) {
        List<String> result = new ArrayList<>();
        for (char ch = 'a'; ch <= 'z'; ch++) {
            for (int i = 0; i < word.length(); ++i) {
                if (ch == word.charAt(i)) continue;
                String newWord = replace(word, i, ch);
                if (dict.contains(newWord)) result.add(newWord);
            }
        }
        return result;
    }
    private String replace(String s, int index, char c) {
        char[] chars = s.toCharArray();
        chars[index] = c;
        return new String(chars);
    }
}

126. Word Ladder II

加强版，百尺竿头更进一步，烦人程度更上一层楼。

要求求出所有最短path，这里面“所有”对应DFS，“最短”对应BFS，疯狂暗示。

两种方式，start到end BFS接着end到start DFS或者start到end DFS接着end到start BFS。不小心说了句废话。

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ladders = new ArrayList<>();
        if (beginWord == null || endWord == null || !wordList.contains(endWord)) return ladders;

        Set<String> dict = new HashSet<>();
        for (String word : wordList) {
            dict.add(word);
        }
        Map<String, List<String>> map = new HashMap<>();
        Map<String, Integer> distance = new HashMap<>();

        bfs(map, distance, beginWord, endWord, dict);

        List<String> path = new ArrayList<>();

        dfs(ladders, path, endWord, beginWord, distance, map);

        return ladders;
    }
    private void dfs(List<List<String>> ladders, List<String> path, String crt,
            String start, Map<String, Integer> distance,
            Map<String, List<String>> map) {
        path.add(crt);
        if (crt.equals(start)) {
            Collections.reverse(path);
            ladders.add(new ArrayList<String>(path));
            Collections.reverse(path);
        } else {
            for (String next : map.get(crt)) {
                if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) { 
                    dfs(ladders, path, next, start, distance, map);
                }
            }           
        }
        path.remove(path.size() - 1);
    }
    private void bfs(Map<String, List<String>> map, Map<String, Integer> distance,
            String start, String end, Set<String> dict) {
        Queue<String> q = new LinkedList<>();
        q.offer(start);
        distance.put(start, 0);
        for (String s : dict) {
            map.put(s, new ArrayList<String>());
        }
        while (!q.isEmpty()) {
            String crt = q.poll();

            List<String> nextList = expand(crt, dict);
            for (String next : nextList) {
                map.get(next).add(crt);
                if (!distance.containsKey(next)) {
                    distance.put(next, distance.get(crt) + 1);
                    q.offer(next);
                }
            }
        }
    }
    List<String> expand(String crt, Set<String> dict) {
        List<String> expansion = new ArrayList<>();

        for (int i = 0; i < crt.length(); i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch != crt.charAt(i)) {
                    String expanded = crt.substring(0, i) + ch + crt.substring(i + 1);
                    if (dict.contains(expanded)) {
                        expansion.add(expanded);
                    }
                }
            }
        }
        return expansion;
    }
}