题目描述

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。
转换后得到的单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

样例

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

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

算法1

(BFS建图+DFS搜索)

• 在单词接龙的基础上，建图后直接从终点开始往前搜索即可

* 为什么要从终点开始搜索：dist数组存储的是某个点到起点的距离，从终点开始搜索可以当成判断合法性的条件
* 从终点搜索到起点需要把答案数组反转
* DFS搜索：改变一个点的某个字符，如果改变后的单词在图中，且新点到起点的距离比前一个点到起点的距离少1

Java 代码

class Solution {
    Set<String> set = new HashSet<>();
    Map<String,Integer> dist = new HashMap<>();
    Queue<String> q = new LinkedList<>();
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    String beginWord;
    public List<List<String>> findLadders(String _beginWord, String endWord, List<String> wordList) {
        for(String word: wordList) set.add(word);
        beginWord = _beginWord;
        dist.put(beginWord,0);
        q.offer(beginWord);
        while(q.size() != 0){
            String s = q.poll();
            for(int i = 0; i < s.length(); i++){
                char[] c = s.toCharArray();
                for(char j = 'a'; j <= 'z'; j++){
                    c[i] = j;
                    String t = new String(c);
                    if(set.contains(t) && !dist.containsKey(t)){
                        dist.put(t,dist.get(s)+1);
                        if(t.equals(endWord)) break;
                        q.offer(t);
                    }
                }
            }
        }
        if(!dist.containsKey(endWord)) return res;
        path.add(endWord);
        dfs(endWord);
        return res;
    }

    void dfs(String u){
        if(u.equals(beginWord)){
            Collections.reverse(path);
            res.add(new ArrayList<>(path));
            Collections.reverse(path);
        }
        for(int i = 0; i < u.length(); i++){
            char[] c = u.toCharArray();
            for(char j = 'a'; j <= 'z'; j++){
                c[i] = j;
                String t = new String(c);
                if(dist.containsKey(t) && dist.get(t)+1 == dist.get(u)){
                    path.add(t);
                    dfs(t);
                    path.remove(path.size()-1);
                }
            }
        }
    }
}