代码随想录：110、字符串接龙

110. 字符串接龙

这道题使用bfs，一个map存是否走过该字符串，set集合存储所有字符串，从beginstr开始，改变每一位的字符，如果新字符在set中，加入队列，更新path。

1、条件准备

s存所有字符串，visit存到某字符串的最短距离。

初始把beginstr的距离为1加入

  string beginstr,endstr,str;int n;cin>>n;unordered_set<string> s;cin>>beginstr>>endstr;rep(i,1,n){cin>>str;s.insert(str);}unordered_map<string,int> visit;visit.insert({beginstr,1});

2、bfs

把起始字符串放入队列。bfs，path为当前字符串的最短距离。

逐个更改每个字符，如果新字符在set中并且没访问过，加入队列中。

如果新字符为endstr则输出。

bfs没找到则输出0

 queue<string> q;q.push(beginstr);while(!q.empty()){string cur=q.front();q.pop();int path=visit[cur];rep(i,0,cur.size()){string t=cur;for(int j=0;j<26;j++){t[i]=j+'a';if(t==endstr){cout<<(path+1);return 0;}if(s.find(t)!=s.end()&&visit.find(t)==visit.end()){visit.insert({t,path+1});q.push(t);}}}}cout<<'0';

3、总结

这个题使用bfs来计算最短路径。

完整代码如下：

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string beginstr,endstr,str;int n;cin>>n;unordered_set<string> s;cin>>beginstr>>endstr;rep(i,1,n){cin>>str;s.insert(str);}unordered_map<string,int> visit;visit.insert({beginstr,1});queue<string> q;q.push(beginstr);while(!q.empty()){string cur=q.front();q.pop();int path=visit[cur];rep(i,0,cur.size()){string t=cur;for(int j=0;j<26;j++){t[i]=j+'a';if(t==endstr){cout<<(path+1);return 0;}if(s.find(t)!=s.end()&&visit.find(t)==visit.end()){visit.insert({t,path+1});q.push(t);}}}}cout<<'0';return 0;
}