代码随想录: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;
}
原文地址:https://blog.csdn.net/qq_74924951/article/details/142696162
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!