Word Ladder I & II

Word Ladder I

著名 gay 题，时间复杂度爆炸的典范，也是目前我知道的 leetcode 题里唯一一道非常适合使用 bi-directional bfs 的问题。

比较独特的是这题不是 DFS + Backtracking，主要原因在于我们要确保 “路线最短” ，这个更适合用 BFS 解决，两层字典首次相交的地方一定是最短路线。

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if(beginWord.length() != endWord.length()) return 0;
        if(wordList == null || wordList.size() == 0) return 0;
        if(beginWord.equals(endWord)) return 2;

        HashSet<String> beginSet = new HashSet<String>();
        HashSet<String> endSet = new HashSet<String>();

        beginSet.add(beginWord);
        endSet.add(endWord);

        wordList.remove(beginWord);
        wordList.remove(endWord);

        return bfs(2, beginSet, endSet, wordList);
    }

    private int bfs(int steps, Set<String> beginSet, Set<String> endSet, Set<String> wordSet){

        HashSet<String> nextLevel = new HashSet<String>();

        for(String beginWord : beginSet){
            char[] charArray = beginWord.toCharArray();
            for(int pos = 0; pos < charArray.length; pos++){
                for(char chr = 'a'; chr <= 'z'; chr++){
                    charArray[pos] = chr;
                    String str = String.valueOf(charArray);
                    if(endSet.contains(str)) return steps;

                    if(wordSet.contains(str)){
                        nextLevel.add(str);
                        wordSet.remove(str);
                    }
                }
                charArray = beginWord.toCharArray();
            }
        }
        if(nextLevel.size() == 0) return 0;

        if(endSet.size() < nextLevel.size()){
            return bfs(steps + 1, endSet, nextLevel, wordSet);
        } else {
            return bfs(steps + 1, nextLevel, endSet, wordSet);
        }
    }
}

除了递归之外，还可以用迭代。反正迭代的 BFS 好写。

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if(beginWord.length() != endWord.length()) return 0;
        if(wordList == null || wordList.size() == 0) return 0;
        if(beginWord.equals(endWord)) return 2;

        HashSet<String> beginSet = new HashSet<String>();
        HashSet<String> endSet = new HashSet<String>();

        beginSet.add(beginWord);
        endSet.add(endWord);

        wordList.remove(beginWord);
        wordList.remove(endWord);

        int steps = 2;

        while(!beginSet.isEmpty()){
            HashSet<String> nextLevel = new HashSet<String>();
            for(String word : beginSet){
                char[] charArray = word.toCharArray();
                for(int pos = 0; pos < charArray.length; pos++){
                    for(char chr = 'a'; chr <= 'z'; chr++){
                        charArray[pos] = chr;
                        String str = String.valueOf(charArray);
                        if(endSet.contains(str)) return steps;

                        if(wordList.contains(str)){
                            nextLevel.add(str);
                            wordList.remove(str);
                        }
                    }
                    charArray = word.toCharArray();
                }
            }

            steps ++;
            if(nextLevel.size() < endSet.size()){
                beginSet = nextLevel;
            } else {
                beginSet = endSet;
                endSet = nextLevel;
            }
        }

        return 0;
    }
}

Word Ladder II

LeetCode 著名 gay 题的加强版，烦人程度更上一层楼。。。当要返回所有 path 的时候，细节处理就更多了。其实这题和 Longest Increasing Subsequence 的 follow-up ，返回所有 LIS 有相通的地方，都是维护一个 Directed Graph 关系并且从某一个终点进行 dfs 返回所有 valid path.

这题的最终解法是一个 Bi-directional BFS 与 DFS 的结合，因为 bfs 过程中起点终点会调换，为了保证 path 的正确性要 keep track of direction.

有向图找最短距离用 BFS

有向图返回所有路径用 DFS

HashMap 中 value 是 List 可以直接map.get(key).add(value);

public class Solution {

    boolean isConnected = false;

    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {

        Set<String> top = new HashSet<String>();
        top.add(beginWord);

        Set<String> bot = new HashSet<String>();
        bot.add(endWord);

        Map<String, List<String>> map = new HashMap<String, List<String>>();
        // BFS 在这里只是起到一个更新 hashmap 的作用，hashmap 存着所有有效的 adjacency list
        bfs(top, bot, wordList, false, map);

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

        if(!isConnected) return rst;

        List<String> list = new ArrayList<String>();
        list.add(beginWord);

        // DFS 负责返回并写入所有 paths
        dfs(rst, list, beginWord, endWord, map);

        return rst;
    }

    // @param swap: whether we are pointing at the right direction, start->end
    //              since we use bi-directional BFS it's necessary to keep track of 
    //              directions in hashmap to construct paths
    public void bfs(Set<String> top, Set<String> bot, Set<String> dict, boolean swap, Map<String, List<String>> map){

        HashSet<String> nextLevel = new HashSet<String>();

        // 避免搜索重复元素，免得搜索路径上出现环
        dict.removeAll(top);
        dict.removeAll(bot);

        for(String src : top){
            for(int pos = 0; pos < src.length(); pos++){
                char[] array = src.toCharArray();
                for(char chr = 'a'; chr <= 'z'; chr++){
                    if(array[pos] == chr) continue;
                    array[pos] = chr;
                    String next = String.valueOf(array);

                    // 决定 src 与 next 两个单词的 directed edge 方向
                    String key = (swap) ? next: src;
                    String value = (swap) ? src: next;

                    if(!map.containsKey(key)) map.put(key, new ArrayList<String>());

                    // 前面已经把先后顺序确定了，map更新就老老实实 key - value 就好
                    if(bot.contains(next)){
                        map.get(key).add(value);
                        isConnected = true;
                    }
                    if(dict.contains(next)){
                        map.get(key).add(value);
                        nextLevel.add(next);
                    }
                }
            }

        }

        if(isConnected || nextLevel.size() == 0) return;

        // 这里直接扔 true / false 是不对的，应该用原来传进来的变量 swap 来决定
        if(nextLevel.size() <= bot.size()){
            bfs(nextLevel, bot, dict, swap, map);
        } else {
            bfs(bot, nextLevel, dict, !swap, map);
        }

    }

    public void dfs(List<List<String>> rst, List<String> list, String start, String end, Map<String, List<String>> map){
        if(start.equals(end)){
            rst.add(new ArrayList<String>(list));
            return;
        }

        // 没有这行会导致 null pointer exception，毕竟不是每个 word 都在 hashmap 里
        // word 自己是叶节点，死胡同
        if(!map.containsKey(start)) return;

        for(String next : map.get(start)){
            list.add(next);
            dfs(rst, list, next, end, map);
            list.remove(list.size() - 1);
        }
    }
}