126. Word Ladder II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk].

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Code

class Solution {
    public List<List<String>> findLadders(String start, String end, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();

        HashSet<String> dict = new HashSet<>(wordList);

        HashMap<String, ArrayList<String>> neigh = new HashMap<>();
        HashMap<String, Integer> distance = new HashMap<>();

        dict.add(start);
        build(start, end, dict, neigh, distance);
        search(start, end, neigh, distance, new ArrayList<>(), res);
        return res;
    }

    private void build(
            String start,
            String end,
            Set<String> dict,
            HashMap<String, ArrayList<String>> neigh,
            HashMap<String, Integer> distance) {
        for (String str : dict) {
            neigh.put(str, new ArrayList<>());
        }

        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        distance.put(start, 0);

        while (!queue.isEmpty()) {
            int size = queue.size();
            // 是否找到目标单词
            boolean found = false;
            // current level
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                // 到当前这个单词的最短距离
                int curDistance = distance.get(cur);
                // 得到可以由当前词转化成的词
                ArrayList<String> neighbors = getNeighbors(cur, dict);

                for (String neighbor : neighbors) {
                    // 添加neighbor
                    neigh.get(cur).add(neighbor);
                    // 如果之前没有到达过这个单词, 需要添加最短距离
                    if (!distance.containsKey(neighbor)) {
                        distance.put(neighbor, curDistance + 1);
                        // 找到目标单词, 但是仍然要继续完成本层遍历
                        // 因为有可能有多条路径
                        if (end.equals(neighbor)) {
                            found = true;
                        } else {
                            queue.offer(neighbor);
                        }
                    }
                }
            }

            if (found) break;
        }
    }

    // Find all next level nodes.
    private ArrayList<String> getNeighbors(String word, Set<String> dict) {
        ArrayList<String> res = new ArrayList<>();

        for (int i = 0; i < word.length(); i++) {
            StringBuilder sb = new StringBuilder(word);

            for (char ch = 'a'; ch <= 'z'; ch++) {
                sb.setCharAt(i, ch);
                String newWord = sb.toString();
                // neighbor必须在dict中才是合法的
                if (dict.contains(newWord)) {
                    res.add(newWord);
                }
            }
        }

        return res;
    }

    private void search(
            String cur,
            String end,
            HashMap<String, ArrayList<String>> neigh,
            HashMap<String, Integer> distance,
            ArrayList<String> temp,
            List<List<String>> res) {

        temp.add(cur);
        if (end.equals(cur)) {
            res.add(new ArrayList<>(temp));
        } else {
            for (String next : neigh.get(cur)) {
                // 下一个单词是最短距离到达的
                if (distance.get(next) == distance.get(cur) + 1) {
                    search(next, end, neigh, distance, temp, res);
                }
            }
        }
        // 需要去掉本层的单词
        temp.remove(temp.size() - 1);
    }
}

• Time: O(N * (26 ^ L)), L = len(word), N = len(wordList)
• Space: O(N + K * P), K = number of paths, P = path length