单词接龙-双向广搜

单词接龙

题目链接

LeetCode单词接龙

题意概述

1. 字典 \(wordList\) 中从单词 \(beginWord\) 到 \(endWord\) 的 转换序列 是一个按下述规格形成的序列 \(beginWord -> s_1 -> s_2 -> ... -> s_k：\)

2. 每一对相邻的单词只差一个字母。
   对于 \(1 <= i <= k\) 时，每个 \(si\) 都在 \(wordList\) 中。注意， \(beginWord\) 不需要在 \(wordList\) 中。

3. \(s_k = endWord\)

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

思路

1. 每个单词只能向与它差异一个字母的单词转换，可以把一个单词和它能转换的单词连一条边，那么这道题就是一个最短路的问题

2. 考虑\(bfs\),对于一单词，把它能转化的单词加入队列中（这里的能转化指的是既与该单词相差一个字母，又在wodlist中），直到遇到目标单词，根据\(bfs\)的特性，此时一定是最短路径

3. 过程中可以使用哈希表与字符串形成映射

4. 时间复杂度分析：

   • \(wordlist\)中有\(n\)个元素，单词长度为\(n\)
   • 考虑最坏情况：每个单词每一位都被替换过一次，每个单词有\(26\times len\)种替换的结果，假如答案是\(ans\),那么最后的时间复杂度是要大于\(O(len^{ans})\)的

5. 代码

#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;
}

6. 优化
   • \(bfs\)搜索的节点数是以指数级增长的，所以数据一大就爆了、
   • 考虑从起点和终点开始双向搜索
   • 这样复杂度其实没有变，但是比单向搜索快了不少
7. 优化代码

#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