单词接龙
题目链接
题意概述
-
字典 \(wordList\) 中从单词 \(beginWord\) 到 \(endWord\) 的 转换序列 是一个按下述规格形成的序列 \(beginWord -> s_1 -> s_2 -> ... -> s_k：\)
-
每一对相邻的单词只差一个字母。
对于 \(1 <= i <= k\) 时，每个 \(si\) 都在 \(wordList\) 中。注意， \(beginWord\) 不需要在 \(wordList\) 中。 -
\(s_k = endWord\)
-
给你两个单词 \(beginWord\) 和 \(endWord\) 和一个字典 \(wordList\) ，返回 从 \(beginWord\) 到 \(endWord\) 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 \(0\) 。
思路
-
每个单词只能向与它差异一个字母的单词转换，可以把一个单词和它能转换的单词连一条边，那么这道题就是一个最短路的问题
-
考虑\(bfs\),对于一单词，把它能转化的单词加入队列中（这里的能转化指的是既与该单词相差一个字母，又在wodlist中），直到遇到目标单词，根据\(bfs\)的特性，此时一定是最短路径
-
过程中可以使用哈希表与字符串形成映射
-
时间复杂度分析：
- \(wordlist\)中有\(n\)个元素，单词长度为\(n\)
- 考虑最坏情况：每个单词每一位都被替换过一次，每个单词有\(26\times len\)种替换的结果，假如答案是\(ans\),那么最后的时间复杂度是要大于\(O(len^{ans})\)的
-
代码
#include <bits/stdc++.h>
std::string begin, end;
int n = 0;
const int maxn = 1e5 + 5;
std::unordered_map<std::string, int> wordList;
std::unordered_map<std::string, int> mp;
std::unordered_map<int, std::string> st;
std::queue<int> que;
int dis[maxn];
int cnt = -1;
void bfs()
{
que.push(++cnt);
mp[begin] = cnt;
st[cnt] = begin;
dis[cnt] = 0;
while(!que.empty())
{
int tmp = que.front();
que.pop();
std::string cur = st[tmp];
for (int i = 0; i < (int)cur.length(); i++)
{
for (int j = 0; j <= 25; j++)
{
std::string nxt = cur;
char ch = (char)('a' + j);
if (ch == nxt[i]) continue;
nxt[i] = ch;
if (wordList[nxt] != 0 && mp[nxt] == 0)
{
std::cout << nxt << '\n';
que.push(++cnt);
mp[nxt] = cnt;
st[cnt] = nxt;
dis[cnt] = dis[mp[cur]] + 1;
if (nxt == end)
{
std::cout << dis[cnt] + 1;
return;
}
}
}
}
}
std::cout << 0;
}
signed main()
{
//freopen("in.txt", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::cin >> begin >> end >> n;
std::string str;
memset(dis, -1, sizeof(dis));
for (int i = 1; i <= n; i++)
{
std::cin >> str;
wordList[str] = 1;
}
if (wordList[end] == 0)
{
std::cout << 0;
return 0;
}
bfs();
return 0;
}
- 优化
- \(bfs\)搜索的节点数是以指数级增长的，所以数据一大就爆了、
- 考虑从起点和终点开始双向搜索
- 这样复杂度其实没有变，但是比单向搜索快了不少
- 优化代码
#include <bits/stdc++.h>
std::string begin, end;
const int maxn = 1e5 + 5;
std::unordered_map<std::string, int> wordList;
std::unordered_map<std::string, int> mp;
std::unordered_map<int, std::string> st;
std::queue<int> queA, queB;
int disA[maxn], disB[maxn];
int cnt = -1, n = 0;
int extend(int judge, std::queue<int> &que, int dis[])
{
int ans = 0x7f7f7f7f;
int len = que.size();
for (int l = 0; l < len; l++)
{
int tmp = que.front();
que.pop();
std::string cur = st[tmp];
for (int i = 0; i < (int)cur.length(); i++)
{
std::string nxt = cur;
for (int j = 0; j < 26; j++)
{
char ch = (char)('a' + j);
if (ch == nxt[i]) continue;
nxt[i] = ch;
if (wordList[nxt] == 0) continue;
if (mp[nxt] == 0)
{
mp[nxt] = ++cnt;
st[cnt] = nxt;
dis[cnt] = dis[mp[cur]] + 1;
que.push(cnt);
//std::cout << judge << " " << nxt << '\n';
}
else
{
if (judge == 0 && disA[mp[nxt]] != 0) continue;
if (judge == 1 && disB[mp[nxt]] != 0) continue;
if (judge == 0 && disB[mp[nxt] != 0])
{
//std::cout << nxt << '\n';
ans = std::min(ans, disA[mp[cur]] + disB[mp[nxt]]);
}
if (judge == 1 && disA[mp[nxt]] != 0)
{
//std::cout << nxt << '\n';
ans = std::min(ans, disB[mp[cur]] + disA[mp[nxt]]);
}
}
}
}
}
if (ans != 0x7f7f7f7f) return ans;
return 0;
}
int bfs()
{
queA.push(++cnt);
mp[begin] = cnt, st[cnt] = begin, disA[cnt] = 1;
queB.push(++cnt);
mp[end] = cnt, st[cnt] = end, disB[cnt] = 1;
while(queA.size() && queB.size())
{
int judge = 0, t = 0;
if (queA.size() > queB.size()) // 搜B
{
judge = 1;
t = extend(judge, queB, disB);
}
else // 搜A
{
judge = 0;
t = extend(judge, queA, disA);
}
if (t != 0) return t;
}
return 0;
}
void solve()
{
std::cin >> begin >> end >> n;
std::string str;
for (int i = 1; i <= n; i++)
{
std::cin >> str;
wordList[str] = 1;
}
if (wordList[end] == 0)
{
std::cout << 0;
return;
}
std::cout << bfs();
}
signed main()
{
freopen("in.txt", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
memset(disA, 0, sizeof(disA));
memset(disB, 0, sizeof(disB));
solve();
return 0;
}
示例
输入
hit cog 6
hot dot dog lot log cog
输出
5