leetcode126. 单词接龙 II/图，最短路径_leetcode 无向图最短路径 环形地铁

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

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

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

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

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
1
2
3
4
5
6
7
8
9
10

示例 2:

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

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
1
2
3
4
5
6
7
8

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

基本思想

这道题的关键是，看出问题的本质，求无向图中两个点的最短路径，将能够转化的两个单词连线，构成一个无向图。
当初直接进行的回溯，超时。
下面构造图进行dfs： 超时 19/39

class Solution {
private:
    vector<vector<string>> res;
    unordered_map<string, vector<string>> edge;
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<string> cur;
        unordered_map<string, int> visit;
        cur.push_back(beginWord);
        
        for(int i = 0; i < wordList.size(); ++i){
            for(int j = i + 1; j < wordList.size(); ++j){
                if(diffNum(wordList[i], wordList[j])){
                    edge[wordList[i]].push_back(wordList[j]);
                    edge[wordList[j]].push_back(wordList[i]);
                }
            }
        }
        if(edge.count(beginWord) == 0){//特别注意：起始点有可能在单词表内
            for(int i = 0; i < wordList.size(); ++i){
                if(diffNum(wordList[i], beginWord)){
                    edge[wordList[i]].push_back(beginWord);
                    edge[beginWord].push_back(wordList[i]);
                }
            }
        }
        dfs(cur, wordList, visit, beginWord, endWord);
        return res;
    }
    void dfs(vector<string> cur, vector<string>& wordList, unordered_map<string, int> visit, string curW, string endW){
        if(curW == endW){
            // for(auto c : cur)
            //     cout << c << " " ;
            // cout << endl;
            if(res.empty() || cur.size() < res[0].size()){
                res.clear();
                res.push_back(cur);
            }
            else if(!res.empty() && res[0].size() == cur.size())
                res.push_back(cur);
            return;
        }
        visit[curW] = 1;
        for(int i = 0; i < edge[curW].size(); ++i){
            if(visit[edge[curW][i]] == 0){
                //visit[edge[curW][i]] = 1;
                cur.push_back(edge[curW][i]);
                dfs(cur, wordList, visit, edge[curW][i], endW);
                //visit[edge[curW][i]] = 0;
                cur.pop_back();
            }
        }
        visit[curW] = 0;
    }
    bool diffNum(string& word1, string& word2){
        int res = 0;
        for(int i = 0; i < word1.size() && res < 2; ++i){
            if(word1[i] != word2[i]){
                ++res;
            }            
        }
        return res == 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

bfs求两点间最短路径
这里维护一个数组，用来统计从源节点到该节点的路径长度，因为最后可能有多条最短路径。
队列中保存的是从源节点到当前节点的路径

class Solution {
private:
    vector<vector<string>> res;
    unordered_map<string, vector<string>> edge;
    unordered_map<string,int> dis;
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
       
        
        for(int i = 0; i < wordList.size(); ++i){
            for(int j = i + 1; j < wordList.size(); ++j){
                if(diffNum(wordList[i], wordList[j])){
                    edge[wordList[i]].push_back(wordList[j]);
                    edge[wordList[j]].push_back(wordList[i]);
                    
                }                
            }
            dis[wordList[i]] = 0x3f3f3f3f;
        }
        if(edge.count(beginWord) == 0){//特别注意：起始点有可能在单词表内
            for(int i = 0; i < wordList.size(); ++i){
                if(diffNum(wordList[i], beginWord)){
                    edge[wordList[i]].push_back(beginWord);
                    edge[beginWord].push_back(wordList[i]);
                }
            }
        }
        bfs(beginWord, endWord);
        return res;
    }
    void bfs(string curW, string endW){
        queue<vector<string>> q;
        
        q.push({curW});
        dis[curW] = 0;
        while(!q.empty()){
            int n = q.size();
            while(n--){
                auto temp = q.front();
                q.pop();
                string backs = temp.back();
                if(backs == endW){                    
                    res.push_back(temp);
                    continue;
                }
                for(int i = 0; i < edge[backs].size(); ++i){
                    if(dis[backs] + 1 <= dis[edge[backs][i]]){//特别注意这里
                        dis[edge[backs][i]] = dis[backs] + 1;
                        auto copy(temp);
                        copy.push_back(edge[backs][i]);
                        q.push(copy);
                    }
                }
            }
            if(res.size())
                break;
        }
    }
    bool diffNum(string& word1, string& word2){
        int res = 0;
        for(int i = 0; i < word1.size() && res < 2; ++i){
            if(word1[i] != word2[i]){
                ++res;
            }            
        }
        return res == 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68