LeedCode 127. 单词接龙

一、题目

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

    序列中第一个单词是 beginWord 。
    序列中最后一个单词是 endWord 。
    每次转换只能改变一个字母。
    转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
 

示例 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" 不在字典中，所以无法进行转换。

 

提示：

    1 <= beginWord.length <= 10
    endWord.length == beginWord.length
    1 <= wordList.length <= 5000
    wordList[i].length == beginWord.length
    beginWord、endWord 和 wordList[i] 由小写英文字母组成
    beginWord != endWord
    wordList 中的所有字符串 互不相同

           

二、思路

• 可以把每个单词都看作一个点，至于是否有边，那么就看能否进行转化即相差一个字母，若能转化即有边，对所有单词进行建图，最后bfs求一次最短距离即可。 O(N2)
• 我们简化建图，上面的方法一个顶点最短有N-1条边，我们可以为每个单词增加虚拟节点，如hit即增加3个虚拟节点*it,h*t,hi*,让hit与3个虚拟节点相连接即可，若有单词能够到达hit那么必然与3个虚拟节点有边。于是每个单词最多有C条边，C为单词的长度，复杂度O(NCC) N*C是顶点个数，C是边数。
• 双向BFS：来减少搜索树的长度，从起点和终点同时开始搜索，当某个节点处相遇即是答案。

三、代码

class Solution {
public:
    int minv = 1e6;
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int n = wordList.size();  
        vector<vector<int>> g(n + 1);
        // 对每个单词进行建边
        wordList.push_back(beginWord);
        int end = -1;
        for (int i = 0; i <= n; i++) {
            if (wordList[i] == endWord) end = i;
            for (int j = i + 1; j <= n; j++) {
                if (ok(i, j, wordList)) {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }
        if (end == -1) return 0; //不存在
        // 从编号n开始搜索
        return bfs(n, 1, g, end);
    }
    int bfs(int n, int t, vector<vector<int>>& g, int end) {
        vector<bool> v(n + 1);
        queue<int> q;
        int step = 0;
        q.push(n); 
        v[n] = true;
        while (!q.empty()) {
            int size = q.size();
            step++;
            for (int t = 0; t < size; t++) {
                int u = q.front(); q.pop();
                for (int i = 0; i < g[u].size(); i++) {
                    int nv = g[u][i];
                    if (!v[nv]) {
                        v[nv] = true;
                        q.push(nv);
                        if (nv == end) return step + 1;
                    }
                }
            }
             
        }
        return 0;
    } 


    bool ok(int i, int j, vector<string>& wordList) {
        int cnt = 0;
        for (int k = 0; k < wordList[i].size(); k++) {
            if (wordList[i][k] != wordList[j][k]) cnt++;
        }
        return cnt <= 1;
    }
};


           

class Solution {
public:
    unordered_map<string, int> mp;
    int node_num = 0;
    vector<vector<int>> edge; 
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //构建虚拟节点和边
        wordList.push_back(beginWord);
        for (string& s: wordList) addEdge(s);
        //bfs求最短距离
        if (!mp.count(endWord)) return 0;
        int end = mp[endWord];
        queue<int> q;
        q.push(mp[beginWord]);
        vector<int> dis(node_num, 1e6);
        dis[mp[beginWord]] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < edge[u].size(); i++) {
                int v = edge[u][i];
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                    if (v == end) return dis[v] / 2 + 1;
                }
            }
        }   
        return 0;
    }
    void addNode(string& s) {
        if (!mp.count(s)) {
            mp[s] = node_num++;
            //edge.emplace_back();//增加一个vetor<int>
            edge.push_back(vector<int>(0));
        }
    }
    void addEdge(string& s) {
        addNode(s);
        int idx = mp[s];
        //创建c个虚拟结点
        for (char& c: s) {
            char t = c;
            c = '*';
            addNode(s);
            int idx2 = mp[s];
            edge[idx].push_back(idx2);
            edge[idx2].push_back(idx);
            c = t; //还原字符
        }
    }
};

           

• 双向BFS

class Solution {
public:
    unordered_map<string, int> mp;
    int node_num = 0;
    vector<vector<int>> edge; 
    int MAXSIZE = 1e6;
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //构建虚拟节点和边
        wordList.push_back(beginWord);
        for (string& s: wordList) addEdge(s);
        //bfs求最短距离
        if (!mp.count(endWord)) return 0;
        int end = mp[endWord];
        queue<int> q, q_end;
        q.push(mp[beginWord]);
        q_end.push(end);
        vector<int> dis(node_num, MAXSIZE);
        vector<int> dis_end(node_num, MAXSIZE);
        dis[mp[beginWord]] = 0;
        dis_end[end] = 0;
        while (!q.empty() && !q_end.empty()) {
            int size = q.size();
            for (int t = 0; t < size; t++) {
                int u = q.front(); q.pop();
                for (int i = 0; i < edge[u].size(); i++) {
                    int v = edge[u][i];
                    if (dis[v] > dis[u] + 1) {
                        dis[v] = dis[u] + 1;
                        q.push(v);
                        if (dis_end[v] != MAXSIZE) return (dis[v] + dis_end[v]) / 2 + 1;
                    }
                }
            }
            size = q_end.size();
            for (int t = 0; t < size; t++) {
                int u = q_end.front(); q_end.pop();
                for (int i = 0; i < edge[u].size(); i++) {
                    int v = edge[u][i];
                    if (dis_end[v] > dis_end[u] + 1) {
                        dis_end[v] = dis_end[u] + 1;
                        q_end.push(v);
                        if (dis[v] != MAXSIZE) return (dis[v] + dis_end[v]) / 2 + 1;
                    }
                }
            }
        }   
        return 0;
    }
    void addNode(string& s) {
        if (!mp.count(s)) {
            mp[s] = node_num++;
            //edge.emplace_back();//增加一个vetor<int>
            edge.push_back(vector<int>(0));
        }
    }
    void addEdge(string& s) {
        addNode(s);
        int idx = mp[s];
        //创建c个虚拟结点
        for (char& c: s) {
            char t = c;
            c = '*';
            addNode(s);
            int idx2 = mp[s];
            edge[idx].push_back(idx2);
            edge[idx2].push_back(idx);
            c = t; //还原字符
        }
    }
};