126. Word Ladder II - jiejackyzhang/leetcode-note GitHub Wiki

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 intermediate word must exist in the word list For example,

Given:

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

Return

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

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

解题思路为BFS+DFS。

首先用BFS的方法得到每个word的neighbor的信息。 然后用DFS backtracking的方法得到所有的shortest path。

public class Solution {
    
    private Map<String, List<String>> neighborsMap;
    private Map<String, Integer> distMap;
    
    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        neighborsMap = new HashMap<>();
        distMap = new HashMap<>();
        wordList.add(endWord);
        createGraph(beginWord, endWord, wordList);
        List<String> path = new ArrayList<>();
        path.add(beginWord);
        dfs(res, path, beginWord, endWord, wordList);
        return res;
    }
    
    private void createGraph(String beginWord, String endWord, Set<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        distMap.put(beginWord, 0);
        neighborsMap.put(beginWord, new ArrayList<>());
        for(String word : wordList) {
            neighborsMap.put(word, new ArrayList<>());
        }
        while(!queue.isEmpty()) {
            String word = queue.poll();
            List<String> neighbors = findNeighbor(word, wordList);
            for(String neighbor : neighbors) {
                neighborsMap.get(word).add(neighbor);
                if(!distMap.containsKey(neighbor)) {
                    distMap.put(neighbor, distMap.get(word)+1);
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    private List<String> findNeighbor(String word, Set<String> wordList) {
        List<String> neighbors = new ArrayList<>();
        for(int i = 0; i < word.length(); i++) {
            for(char ch = 'a'; ch <= 'z'; ch++) {
                char[] charArray = word.toCharArray();
                if(charArray[i] == ch) continue;
                charArray[i] = ch;
                String newWord = new String(charArray);
                if(wordList.contains(newWord)) {
                    neighbors.add(newWord);
                }
            }
        }
        return neighbors;
    }
    
    private void dfs(List<List<String>> res, List<String> path, String beginWord, String endWord, Set<String> wordList) {
        if(beginWord.equals(endWord)) {
            res.add(new ArrayList<String>(path));
            return;
        }
        for(String neighbor : neighborsMap.get(beginWord)) {
            if(distMap.get(neighbor) == distMap.get(beginWord)+1) {
                path.add(neighbor);
                dfs(res, path, neighbor, endWord, wordList);
                path.remove(path.size()-1);
            }
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️