Word Ladder II

Question

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Solution

九章算法課有教過這題，是 Word Ladder 的 follow up 題目，透過 BFS + DFS 來實現。第一次遍歷的 BFS (Queue + HashMap) 會將每個點距離終點的 distance 還有各自的 neighbors 找到，接著再從終點往回用 DFS 走第二次遍歷。 要小心處理的地方有：

1. 在 BFS 的更新 neighbor list 的時候，記得要先判斷一下 map.get(next) 是否為 null (感覺這個判斷多做了，九章的解答有在一開頭把 endWord 加進 wordList 裡面，但我照著這樣做會出現最後一個 test case 跑不過的問題)

2. 在 DFS 裡把 path 加進 ladder 時，要記得用 Collections.reverse、deep copy path、最後 path.remove(path.size() - 1)

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ladders = new ArrayList<List<String>>();
        Map<String, List<String>> neighbors = new HashMap<String, List<String>>();
        Map<String, Integer> distance = new HashMap<String, Integer>();

        wordList.add(beginWord);

        bfs(neighbors, distance, beginWord, endWord, wordList);

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

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

        return ladders;
    }

    public void bfs(Map<String, List<String>> neighbors, Map<String, Integer> distance, String start, String end, List<String> dict) {
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        distance.put(start, 0);

        for (String s : dict) {
            neighbors.put(s, new ArrayList<String>());
        }

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String crt = queue.poll();
                List<String> nextList = helper(crt, dict);
                for (String next : nextList) {
                    if (neighbors.get(crt) == null) {
                        neighbors.put(crt, new ArrayList<String>());
                    }
                    neighbors.get(crt).add(next);
                    if (!distance.containsKey(next)) {
                        distance.put(next, distance.get(crt) + 1);
                        queue.offer(next);
                    }
                }
            }
        }
    }

    public List<String> helper(String crt, List<String> dict) {
        ArrayList<String> res = new ArrayList<String>();
        for (String s : dict) {
            int diff = 0;
            for (int i = 0; i < crt.length(); i++) {
                if (crt.charAt(i) != s.charAt(i)) {
                    if (++diff > 1) {
                        break;
                    }
                }
            }
            if (diff == 1 && !res.contains(s)) {
                res.add(s);
            }
        }
        return res;
    }

    public void dfs(List<List<String>> ladders, List<String> path, String crt, String start, 
                     Map<String, Integer> distance, Map<String, List<String>> neighbors) {
        path.add(crt);
        if (crt.equals(start)) {
            Collections.reverse(path);
            ladders.add(new ArrayList<>(path));
            Collections.reverse(path);
        } else {
            if (neighbors.get(crt) != null) {
                for (String next : neighbors.get(crt)) {
                    if (distance.containsKey(next) && distance.get(next) + 1 == distance.get(crt)) {
                        dfs(ladders, path, next, start, distance, neighbors);
                    }
                }   
            }
        }
        path.remove(path.size() - 1);
    }