传送门
我们记录pos1 pos2 pos3 分别代表现在字符串1,2,3的位置
然后判断pos1是否等于pos3 或者pos2是否等于pos3 分别进行dfs
然后我们发现是可以记忆化的
比方当pos1=pos3且pos2=pos3 那会先搜索pos1+1 那么在这一次的dfs 有可能就提前处理出之后会选择的方式 那么当回溯之后 就会再去走这样的方式 浪费了很多时间
所以只需标记一下vis[pos1][pos2] 之后走到这儿就直接return
#include<bits/stdc++.h> #define N 1005 using namespace std; int n,len1,len2,len3; string s1,s2,s3; bool ans,vis[N][N]; void dfs(int pos1,int pos2,int pos3) //在字符串1 2 3 中的位置 { if(pos1==len1&&pos2==len2) //已经超出了 { ans=true; return; } if(s1[pos1]!=s3[pos3]&&s2[pos2]!=s3[pos3]) return; if(vis[pos1][pos2]) return; //中途截断 vis[pos1][pos2]=true; if(s1[pos1]==s3[pos3]) dfs(pos1+1,pos2,pos3+1); if(s2[pos2]==s3[pos3]) dfs(pos1,pos2+1,pos3+1); } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n; for(int i=1;i<=n;i++) { cin>>s1>>s2>>s3; memset(vis,false,sizeof(vis)); ans=false; len1=s1.length(); len2=s2.length(); len3=s3.length(); dfs(0,0,0); if(ans) cout<<"Data set "<<i<<": yes"<<endl; else cout<<"Data set "<<i<<": no"<<endl; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9810405.html
