leetcode 126. 单词接龙 II

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 126. 单词接龙 II，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1909字，纯文字阅读大概需要3分钟。

内容图文

题目传送门

力扣
链接：https://leetcode-cn.com/problems/word-ladder-ii/

题解：
根据题意，首先我们得看一下endWord在不在list中，如果不在直接返回一个空的即可。如果在的话，那么我们可以先用bfs跑一边，求出beginWord到endWord的距离，同时也求出了beginWord到中间路径上的点的距离，当所有距离计算出来之后，我们只需要从endWord反向dfs搜索一遍，每次变换一个字符，如果变换之后存在这个字符串并且已经计算过距离且距离之差为1，那么就搜下去。

之所以要判断距离，是因为如果该字符串没有记录过距离，那么说明不可能从beginWord转移过来，肯定是找不到答案的

Code：

```class Solution {
public:

    vector<vector<string>> res;
    vector<string> path;
    unordered_map<string, int> dist;
    unordered_set<string> set;
    queue<string> q;

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        for (string s : wordList) set.insert(s);
        set.insert(beginWord);

        if (!set.count(endWord)) return res;

        dist[beginWord] = 0; // 距离自己长度0
        q.push(beginWord);
        while (q.size()) {
            auto t = q.front();
            q.pop();
            string backup = t;
            for (int i = 0; i < t.size(); i ++ ) {
                t = backup;
                for (char c = 'a'; c <= 'z'; c ++ ) { // 枚举变换规则
                    t[i] = c;
                    if (set.count(t) && dist.count(t) == 0) { // 如果之前没记录过距离就说明是最近的路径到的这个点
                        dist[t] = dist[backup] + 1;
                        if (t == endWord) break; // 到了终点就不用在搜下去了，其余的点距离起始位置最小也是和endWord一样，那么即使下一个即使endWord，也不是最小的路径
                        q.push(t);
                    }
                }
            }
        }

        path.push_back(endWord); // 从答案往回搜

        dfs(endWord, beginWord);
        return res;
    }

    void dfs(string s, string target) {
        if (s == target) {
            reverse(path.begin(), path.end()); // 因为是反着放的，逆转一下
            res.push_back(path);
            reverse(path.begin(), path.end());
        } else {
            string backup = s;
            for (int i = 0; i < s.size(); i ++ ) {
                s = backup;
                for (char c = 'a'; c <= 'z'; c ++ ) { // 枚举变换
                    s[i] = c;
                    if (set.count(s) && dist[s] + 1 == dist[backup]) { // 变换之后必须保证单词存在，而且能从起点转移过来
                        path.push_back(s);
                        dfs(s, target);
                        path.pop_back();
                    }
                }
            }
        }
    }

};

内容总结

以上是互联网集市为您收集整理的leetcode 126. 单词接龙 II全部内容，希望文章能够帮你解决leetcode 126. 单词接龙 II所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---