126 Word Ladder II

126. Word Ladder II

1. 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:

1. Only one letter can be changed at a time

2. Each transformed word must exist in the word list. Note that

   beginWord is not a transformed word.

For example,

Given: beginWord="hit" endWord="cog" wordList=["hot","dot","dog","lot","log","cog"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• Return an empty list if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

• You may assume no duplicates in the word list.

• You may assume beginWord and endWord are non-empty and are not the same.

2. Implementation

(1) BFS + Backtracking

思路:

(1）利用BFS找到最短路径，和每个word的邻近的word

(2) 通过回溯法，找出所有的路径

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

        Set<String> dict = new HashSet<>(wordList);
        Map<String, List<String>> neighbors = new HashMap<>();
        Map<String, Integer> distance = new HashMap<>();

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

        dict.add(beginWord);

        getMinPathByBFS(beginWord, endWord, dict, neighbors, distance);
        path.add(beginWord);
        getAllPathsByDFS(beginWord, endWord, neighbors, distance, path, res);
        return res;
    }

    public void getMinPathByBFS(String start, String end, Set<String> dict, Map<String, List<String>> neighbors, Map<String, Integer> distance) {
        for (String word : dict) {
            neighbors.put(word, new ArrayList<>());
        }

        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        distance.put(start, 0);
        boolean minLevel = false;

        while (!queue.isEmpty() && !minLevel) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String curWord = queue.remove();
                int curDist = distance.get(curWord);

                List<String> nextWords = getNeighbors(curWord, dict);

                for (String nextWord : nextWords) {
                    neighbors.get(curWord).add(nextWord);

                    if (!distance.containsKey(nextWord)) {
                        distance.put(nextWord, curDist + 1);

                        if (nextWord.equals(end)) {
                            minLevel = true;
                        }
                        else {
                            queue.add(nextWord);
                        }
                    }
                }
            }
        }
    }

    public List<String> getNeighbors(String word, Set<String> dict) {
        List<String > res = new ArrayList<>();
        char[] letters = word.toCharArray();

        for (int i = 0; i < word.length(); i++) {
            char oldC = letters[i];

            for (char c = 'a'; c <= 'z'; c++) {
                if (letters[i] == c) {
                    continue;
                }
                letters[i] = c;

                String nextWord = new String(letters);

                if (dict.contains(nextWord)) {
                    res.add(nextWord);
                }
            }
            letters[i] = oldC;
        }
        return res;
    }

    public void getAllPathsByDFS(String start, String end, Map<String, List<String>> neighbors, Map<String, Integer> distance, List<String> path, List<List<String>> res) {
        if (start.equals(end)) {
            res.add(new ArrayList<String>(path));
            return;
        }

        for (String neighbor : neighbors.get(start)) {
            if (distance.get(neighbor) == distance.get(start) + 1) {
                path.add(neighbor);
                getAllPathsByDFS(neighbor, end, neighbors, distance, path, res);
                path.remove(path.size() - 1);
            }
        }
    }
}

3. Time & Space Complexity

BFS + Backtracking: 时间复杂度? , 空间复杂度?