题目描述

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

• 1、每次转换只能改变一个字母。
• 2、转换后得到的单词必须是字典中的单词

说明:

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

样例

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

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

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

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

算法分析

bfs + dfs
粗暴解法

• 1、用哈希表记录每个单词到终点 endWord 的最短距离
• 2、从终点 endWord 出发，bfs所有点到终点endWord的最短距离，则起点的距离代表的是起点 beginWord 到终点 endWord 的最短距离，再从起点出发，进行dfs深搜，若下一个单词word能与当前单词s连一条边，且dist[s] = dist[word] + 1，则dist[s]是从dist[word]转移过来的，因此将word记录到当前路径，并继续从word单词进行深搜
• 3、递归过程中注意需要回溯
• 4、若wordList中没有beginWord这个单词，需要将该单词添加进去

个人的写法，有点慢hh，仅供参考

时间复杂度

不会分析

Java 代码

class Solution {
    static List<List<String>> ans = new ArrayList<List<String>>();
    static List<String> path = new ArrayList<String>();
    //判断两个单词是否能连上一条边
    static boolean check(String a, String b)
    {
        int cnt = 0;
        for(int i = 0;i < a.length();i ++)
        {
            if(a.charAt(i) != b.charAt(i))
                cnt ++;
        }
        if(cnt == 1) return true;
        return false;
    }
    static void dfs(String s, List<String> wordList, HashMap<String, Integer> dist)
    {
        if(dist.get(s) == 0)
        {
            ans.add(new ArrayList<String>(path));
            return ;
        }
        for(String word : wordList)
        {
            if(dist.containsKey(word) && check(s, word) && dist.get(s) == dist.get(word) + 1)
            {
                path.add(word);
                dfs(word, wordList, dist);
                path.remove(path.size() - 1);
            }
        }
    }
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        ans.clear();

        boolean flag = false;//不存在beginWord
        for(String word : wordList)
        {
            if(word.equals(beginWord))
            {
                flag = true;
                break;
            }
        }
        if(!flag) wordList.add(beginWord);

        HashMap<String, Integer> dist = new HashMap<String, Integer>();
        dist.put(endWord, 0);
        Queue<String> q = new LinkedList<String>();
        q.add(endWord);
        while(!q.isEmpty())
        {
            String t = q.poll();
            for(String word : wordList)
            {
                if(!dist.containsKey(word) && check(t, word))
                {
                    dist.put(word, dist.get(t) + 1);
                    q.add(word);
                }
            }
        }
        if(!dist.containsKey(beginWord)) return ans;
        path.add(beginWord);
        dfs(beginWord, wordList, dist);
        path.remove(path.size() - 1);
        return ans;
    }
}