P1019 单词接龙

这道题建议直接看董晓或涂老师两位大佬的讲解

这里只是梳理个人的做题思路

思路：

DFS深搜

判断两个字符串可否拼接：

substr+for循环找到最小拼接长度

记得回溯

减少字符串拷贝操作

比如：不需要记录最终字符串，再输出长度

不需要tmp=ans+s[i].substr(subl,s[i].length()-subl)，dfs(tmp)

#include<bits/stdc++.h>
using namespace std;
int n,book[25],res;//res最终长度 
string s[25],begn;//begin龙头字母 int check(string str1,string str2)//check(str1,str2) 返回最小拼接长度 
{int l1=str1.length(),l2=str2.length(),mn=min(l1,l2);string sub1,sub2;for(int k=1;k<=mn;++k){sub1=str1.substr(l1-k,k);sub2=str2.substr(0,k);if(sub1==sub2){if(k==mn) return 0;return k;}}return 0;
}void dfs(string ans)
{int anslen,subl;anslen=ans.length();res=max(res,anslen);//遍历每一种可能 for(int i=1;i<=n;++i){if(book[i]<2){subl=check(ans,s[i]);if(subl>0){book[i]++;//直接将字符串传递给下一轮 //减少大量的字符串拷贝  dfs(ans+s[i].substr(subl,s[i].length()-subl));book[i]--;									  }}}
}int main()
{cin>>n;for(int i=1;i<=n;++i){cin>>s[i];}cin>>s[0];s[0]=' '+s[0];dfs(s[0]);cout<<res-1;return 0;
}