[数据结构与算法]【DFS】单词接龙

• 博客主页: https://blog.csdn.net/qq_50285142
• 欢迎点赞👍收藏?关注?留言 📝 如有错误，敬请指正
• 🎈虽然生活很难，但我们也要一直走下去🎈

原题链接

思路:
$f[i][j]$数组表示第i个单词和第j个单词能重合的字母数（前后缀匹配的位数）
$used[i]$表示第i个单词使用的次数
$dfs()$中参数的含义 ：
$s$ :代表已经拼接好的字符串
$cur$:表示当前拼接好的字符串的末尾用到的是第$cur$个单词

首先对所有的单词两两求一下两个单词拼接在一起的前后缀匹配的长度。
之后dfs每次单词匹配时记录一下单词使用的次数，当单词使用的次数小于2时，且前后缀有匹配长度且没有包含关系时可以拼接下一个单词，每个字符串对能够拼接的所有的单词进行dfs
注意dfs之后需要将单词使用的次数回溯一下，就是把单词的使用次数减回去

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int> pii;

const int dx[] = {-1,-2,-2,-1,1,2,2,1};
const int dy[] = {-2,-1,1,2,2,1,-1,-2};
const int N = 1e5+5,M = 1e5+5;
int n,m,k,res;
string word[25];
int f[25][25],used[25];


void dfs(string s,int cur)
{
	res = max(res,(int)s.size());
	used[cur] ++ ;
	
	for(int i=1;i<=n;i++)
	{
		if(f[cur][i] && used[i]<2)
			dfs(s + word[i].substr(f[cur][i]),i);
	}
	used[cur] --;
	
}

void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>word[i];
	char st;
	cin>>st;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			string a = word[i],b = word[j];
			int sz = min(a.size(),b.size());
			for(int k=1;k<sz;k++)
			{
				if(a.substr(a.size()-k,k)==b.substr(0,k))
				{
					f[i][j] = k;
					break;
				}
			}
		}
	
	for(int i=1;i<=n;i++)
		if(word[i][0]==st)
			dfs(word[i],i);
	cout<<res<<'\n'; 
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	int _;
//	cin>>_;
	_ = 1;
	while(_--)
	{
		solve();
	 } 
	return 0;
 } 

往期优质文章推荐

• 💛💚C++ STL详解，超全总结(快速入门STL)
• 💛🧡【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）
• 💛💚区间贡献问题习题详解