错误代码:
做法的思路没有问题,使用邻接表构造链表,然后找以l,r开头的字符串,然后找这两个字符串的共同后缀子串,但是,我错误的原因在于可能有很多节点对应同一个字母,当一个字母出现多次时,我记录的字母映射的下标为最后一个字母的id值,所以这样一定错了,所以本题目应该将寻找共同后缀子串和节点下标结合起来!!!
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N];
string w[N];
unordered_map<int,string>h1;
unordered_map<string,int>h2,h3;
string l,r;
int n;
int id=0,idx;
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool st[N];
string dfs(int a){
string s=w[a];
st[a]=true;
for(int i=h[a];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
s+=dfs(j);
}
}
return s;
}
int main(){
cin>>l>>r>>n;
memset(h,-1,sizeof h);
for(int i=0;i<n;i++){
string a,b,c;
cin>>a>>b>>c;
if(!h2.count(a)){
id++;
h2[a]=id;
}
h1[h2[a]]=a;
w[h2[a]]=b;
h3[b]=h2[a];
if(!h2.count(c)){
id++;
h2[c]=id;
}
h1[h2[c]]=c;
add(h2[a],h2[c]);
}
string s1=dfs(h2[l]);
memset(st,false,sizeof st);
string s2=dfs(h2[r]);
string temp;
for(int i=s1.size()-1,j=s2.size()-1;i>=0&&j>=0;i--,j--){
if(s1[i]==s2[j]){
temp=s1[i];
}
else{
break;
}
}
if(temp.size()==0)
cout<<"-1";
else{
cout<<h1[h3[temp]];
}
return 0;
}
AC 代码:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int h1, h2, ne[N];
char e[N];
bool st[N];
int main()
{
cin>>h1>>h2>>n;
for(int i=0;i<n;i++){
int a,b;
char c;
cin>>a>>c>>b;
e[a]=c;
ne[a]=b;
}
for(int i=h1;i!=-1;i=ne[i]){
st[i]=true;
}
for(int i=h2;i!=-1;i=ne[i]){------------》这个地方我原本有疑问:这不是从前向后找第一个相同字母的节点嘛,如果后边的节点有不一样的,这也不是共同的后缀字串啊
-----》我有上边的问题还是ne[]数组的认知不到位,一旦第一个共同节点确定了,那么后续的所有节点都是一样的!!!
if(st[i]){
printf("%05d",i);
return 0;
}
}
cout<<-1;
return 0;
}