LeetCode算法 单词接龙 和 单词接龙|| C++_c++头歌最短单词接龙

题目 单词接龙

字典 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。
1
2
3

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。
1
2
3

提示：

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

参考答案

typedef unsigned int uint;
const int N=5005,L0=10,L=N*4; const uint mul=131;
int vis[N],q[N],v1; uint hsh[N],mul1[L0];
vector<int> v[L];
namespace Hash{
	const uint S=16,S1=32-S,M=1996090921;
	struct node{
		int x,t;
		vector<int> *y;
	}h[(1<<S)+1005];
	int T=1;
	inline void insert(int x,int y){
		node *p=h+((uint)x*M>>S1);
		for (;p->t==T;++p)
			if (p->x==x){p->y->push_back(y); return;}
		p->t=T; p->x=x; p->y=v+(v1++); p->y->push_back(y);
	}
	inline vector<int>** find(int x){
		for (node *p=h+((uint)x*M>>S1);p->t==T;++p)
			if (p->x==x)return &p->y;
		return 0;
	}
} using namespace Hash;

class Solution {
public:
	int ladderLength(string beginWord, string endWord, vector<string>& w) {
		for (int i=0;i<v1;++i)v[i].clear();
		int n=w.size(); v1=0; ++T;
		for (int i=0;i<n-1;++i)
			if (w[i]==endWord)swap(w[i],w[n-1]);
		if (w[n-1]!=endWord)return 0;
		w.push_back(beginWord); ++n;
		mul1[0]=1; for (int i=1;i<L0;++i)mul1[i]=mul1[i-1]*mul;
		for (int i=0;i<n;++i){
			int l=w[i].size(); uint h0=0;
			for (char *p=&w[i][0],*end=p+l;p!=end;++p)h0=h0*mul+*p;
			for (char *p=&w[i][0],*end=p+l;p!=end;++p){
				uint h1=h0-*p*mul1[end-1-p];
				insert(h1,i);
			}
			hsh[i]=h0;
		}
		for (int i=0;i<n;++i)vis[i]=0; vis[n-1]=1;
		int l=0,r=1,ans=1; q[0]=n-1;
		while (l<r){
			int r1=r; ++ans;
			for (;l<r;++l){
				int i=q[l]; uint h0=hsh[i];
				for (char *p=&w[i][0],*end=p+w[i].size();p!=end;++p){
					uint h1=h0-*p*mul1[end-1-p];
					vector<int>** pt=find(h1);
					if (*pt){
						vector<int> &vec=*(*pt);
						for (int j:vec)
							if (!vis[j]){
								q[r1++]=j,vis[j]=1;
								if (j==n-2)return ans;
							}
						*pt=0;
					}
				}
			}
			l=r; r=r1;
		}
		return 0;
	}
};
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

题目 单词接龙||

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s₁ -> s₂ -> … -> s_k 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。

转换过程中的每个单词 s_i（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。

s_k == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s₁, s₂, …, s_k] 的形式返回。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
1
2
3
4
5

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。 
1
2
3

提示：

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

参考答案

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>


using namespace std;

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
        vector<vector<string>> res;
        // 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
        unordered_set<string> dict = {wordList.begin(), wordList.end()};
        // 修改以后看一下，如果根本就不在 dict 里面，跳过
        if (dict.find(endWord) == dict.end()) {
            return res;
        }
        // 特殊用例处理
        dict.erase(beginWord);

        // 第 1 步：广度优先遍历建图
        // 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层
        unordered_map<string, int> steps = {{beginWord, 0}};
        // 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
        unordered_map<string, set<string>> from = {{beginWord, {}}};
        int step = 0;
        bool found = false;
        queue<string> q = queue<string>{{beginWord}};
        int wordLen = beginWord.length();
        while (!q.empty()) {
            step++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                const string currWord = move(q.front());
                string nextWord = currWord;
                q.pop();
                // 将每一位替换成 26 个小写英文字母
                for (int j = 0; j < wordLen; ++j) {
                    const char origin = nextWord[j];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        nextWord[j] = c;
                        if (steps[nextWord] == step) {
                            from[nextWord].insert(currWord);
                        }
                        if (dict.find(nextWord) == dict.end()) {
                            continue;
                        }
                        // 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，且距离更远的单词，需要将它从 dict 中删除
                        dict.erase(nextWord);
                        // 这一层扩展出的单词进入队列
                        q.push(nextWord);
                        // 记录 nextWord 从 currWord 而来
                        from[nextWord].insert(currWord);
                        // 记录 nextWord 的 step
                        steps[nextWord] = step;
                        if (nextWord == endWord) {
                            found = true;
                        }
                    }
                    nextWord[j] = origin;
                }
            }
            if (found) {
                break;
            }
        }
        // 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
        if (found) {
            vector<string> Path = {endWord};
            dfs(res, endWord, from, Path);
        }
        return res;
    }

    void dfs(vector<vector<string>> &res, const string &Node, unordered_map<string, set<string>> &from,
             vector<string> &path) {
        if (from[Node].empty()) {
            res.push_back({path.rbegin(), path.rend()});
            return;
        }
        for (const string &Parent: from[Node]) {
            path.push_back(Parent);
            dfs(res, Parent, from, path);
            path.pop_back();
        }
    }
};

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92