天天看點
傳回

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; //還原字元
        }
    }
};
leedcode i++ 最短距離 雙向bfs 搜尋
上一篇: 由“RangeError: Invalid status code: 0”錯誤所引發的思考
下一篇: 20090625 單詞

繼續閱讀