LeetCode 127. 单词接龙

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

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

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

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

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。 示例 2:

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

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。 通过次数72,245提交次数162,120

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-ladder 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

BFS 广度优先搜索

中档题 但是 我不会

所以这个博文 还是 分析官方题解 给的答案

方法一：广度优先搜索 + 优化建图

class Solution {
public:
    unordered_map<string, int> wordId;
    vector<vector<int>> edge;
    int nodeNum = 0;

    void addWord(string& word) {
        if (!wordId.count(word)) {
            wordId[word] = nodeNum++;
            edge.emplace_back();
        }
    }

    void addEdge(string& word) {
        addWord(word);
        int id1 = wordId[word];
        for (char& it : word) {
            char tmp = it;
            it = '*';
            addWord(word);
            int id2 = wordId[word];
            edge[id1].push_back(id2);
            edge[id2].push_back(id1);
            it = tmp;
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for (string& word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.count(endWord)) {
            return 0;
        }
        vector<int> dis(nodeNum, INT_MAX);
        int beginId = wordId[beginWord], endId = wordId[endWord];
        dis[beginId] = 0;

        queue<int> que;
        que.push(beginId);
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int& it : edge[x]) {
                if (dis[it] == INT_MAX) {
                    dis[it] = dis[x] + 1;
                    que.push(it);
                }
            }
        }
        return 0;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution { public: unordered_map<string, int> wordId; vector<vector<int>> edge; int nodeNum = 0;

node Num 用来做下标，

使用了虚拟节点，如 hit 不但 插入 hit 到图里，还把 hi* ，h*t， *it 放进图里 所以距离是两倍 最后 return dis[endId] / 2 + 1;

1. 加点addWord

void addWord(string& word) { if (!wordId.count(word)) { wordId[word] = nodeNum++; edge.emplace_back(); } }

把节点 加入边，用 map 结构 unordered_map<string, int> wordId; 存储下标 nodeNum++ 用来记录节点数

同时 edge.emplace_back(); 是 往 edge 加入一个 空 vector 就是 edge[nodeNum-1] 后面把边 可以插进去

2. 加边 addEdge

void addEdge(string& word) { addWord(word); int id1 = wordId[word]; for (char& it : word) { char tmp = it; it = '*'; addWord(word); int id2 = wordId[word]; edge[id1].push_back(id2); edge[id2].push_back(id1); it = tmp; } }

调用加点 addWord

用数字下标代替 string int id1 = wordId[word];

for (char& it : word) { char tmp = it; it = '*'; addWord(word); 。。。 it = tmp; }

把替代的 * 的虚拟节点 加入 用 it 遍历，后面 it = tmp 恢复 word 原样

int id2 = wordId[word]; edge[id1].push_back(id2); edge[id2].push_back(id1);

获取节点 和虚节点 的下标，存入边内

答案 函数

int ladderLength(string beginWord, string endWord, vector<string>& wordList) { for (string& word : wordList) { addEdge(word); } addEdge(beginWord);

存边 存点

if (!wordId.count(endWord)) { return 0; }

判断 目的 字符串 是否存在

vector<int> dis(nodeNum, INT_MAX); int beginId = wordId[beginWord], endId = wordId[endWord];

string 替换成 id 去匹配

dis[beginId] = 0;

queue<int> que; que.push(beginId);

用 队列实现 广度优先搜索

while (!que.empty()) { int x = que.front(); que.pop(); if (x == endId) { return dis[endId] / 2 + 1; }

搜索到了 就返回

for (int& it : edge[x]) { if (dis[it] == INT_MAX) { dis[it] = dis[x] + 1; que.push(it); } }

没有搜索到 加入 下一层 的 que

}

return 0; } };

方法二：双向广度优先搜索

更快 更高 更强

class Solution {
public:
    unordered_map<string, int> wordId;
    vector<vector<int>> edge;
    int nodeNum = 0;

    void addWord(string& word) {
        if (!wordId.count(word)) {
            wordId[word] = nodeNum++;
            edge.emplace_back();
        }
    }

    void addEdge(string& word) {
        addWord(word);
        int id1 = wordId[word];
        for (char& it : word) {
            char tmp = it;
            it = '*';
            addWord(word);
            int id2 = wordId[word];
            edge[id1].push_back(id2);
            edge[id2].push_back(id1);
            it = tmp;
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for (string& word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.count(endWord)) {
            return 0;
        }

        vector<int> disBegin(nodeNum, INT_MAX);
        int beginId = wordId[beginWord];
        disBegin[beginId] = 0;
        queue<int> queBegin;
        queBegin.push(beginId);

        vector<int> disEnd(nodeNum, INT_MAX);
        int endId = wordId[endWord];
        disEnd[endId] = 0;
        queue<int> queEnd;
        queEnd.push(endId);

        while (!queBegin.empty() && !queEnd.empty()) {
            int queBeginSize = queBegin.size();
            for (int i = 0; i < queBeginSize; ++i) {
                int nodeBegin = queBegin.front();
                queBegin.pop();
                if (disEnd[nodeBegin] != INT_MAX) {
                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1;
                }
                for (int& it : edge[nodeBegin]) {
                    if (disBegin[it] == INT_MAX) {
                        disBegin[it] = disBegin[nodeBegin] + 1;
                        queBegin.push(it);
                    }
                }
            }

            int queEndSize = queEnd.size();
            for (int i = 0; i < queEndSize; ++i) {
                int nodeEnd = queEnd.front();
                queEnd.pop();
                if (disBegin[nodeEnd] != INT_MAX) {
                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1;
                }
                for (int& it : edge[nodeEnd]) {
                    if (disEnd[it] == INT_MAX) {
                        disEnd[it] = disEnd[nodeEnd] + 1;
                        queEnd.push(it);
                    }
                }
            }
        }
        return 0;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最后 答案 函数 不一样

int ladderLength(string beginWord, string endWord, vector<string>& wordList) { for (string& word : wordList) { addEdge(word); } addEdge(beginWord); if (!wordId.count(endWord)) { return 0; }

vector<int> disBegin(nodeNum, INT_MAX); int beginId = wordId[beginWord]; disBegin[beginId] = 0; queue<int> queBegin; queBegin.push(beginId); vector<int> disEnd(nodeNum, INT_MAX); int endId = wordId[endWord]; disEnd[endId] = 0; queue<int> queEnd; queEnd.push(endId);

两套，begin 和 end 两头同时 开始搜索

while (!queBegin.empty() && !queEnd.empty()) { int queBeginSize = queBegin.size(); for (int i = 0; i < queBeginSize; ++i) { int nodeBegin = queBegin.front(); queBegin.pop(); if (disEnd[nodeBegin] != INT_MAX) {

return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1;

顺向搜 到了 nodeBegin 同时 disEnd[nodeBegin] != INT_MAX 逆向的已经 搜索到 nodeBegin 就返回

} for (int& it : edge[nodeBegin]) { if (disBegin[it] == INT_MAX) { disBegin[it] = disBegin[nodeBegin] + 1; queBegin.push(it);

没有出现过的 节点 就 压进去。

} } }

end 同理

int queEndSize = queEnd.size(); for (int i = 0; i < queEndSize; ++i) { int nodeEnd = queEnd.front(); queEnd.pop(); if (disBegin[nodeEnd] != INT_MAX) { return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1; } for (int& it : edge[nodeEnd]) { if (disEnd[it] == INT_MAX) { disEnd[it] = disEnd[nodeEnd] + 1; queEnd.push(it); } } } } return 0; }