蓝桥杯算法训练VIP-单词接龙

题目

题目链接

题解

DFS。

真没想到居然是暴力搜索，感觉时间复杂度根本不允许啊。

大致思路：每次递归都遍历全部字符串，对于每个字符串，枚举要匹配的长度，在此长度下依次匹配原串的尾与遍历到的字符串的头，完全相同说明可以匹配当前长度，就继续深搜。

注意：允许一个字符串用两次。

还是觉得离谱。

代码

#include<bits/stdc++.h>
using namespace std;

int n, ans, vis[30];
string s[30];
char ch;

void dfs(string str, int sum) { // str为已得字符串，即当前拼接方式下得到的字符串   sum为其长度，即sum = str.size() 
	ans = max(ans, sum);
	
	int strsz = str.size();
	for(int i = 1;i <= n;i ++) {
		if(vis[i] > 1) continue;
		
		int ssz = s[i].size();
		int m = min(strsz, ssz);
		
		for(int len = 1;len <= m;len ++) { // 枚举匹配的子串长度为len 
			int j;
			for(j = 0;j < len;j ++) if(str[strsz-len+j] != s[i][j]) break; // 将遍历的字符串的前len个与已得字符串的后len个进行一一比较，若存在不相同的则break 
			
			if(j == len) { // 长度为len时可以接龙 
				string tmp = str;
				for(int k = j;k < ssz;k ++) tmp += s[i][k]; // 将枚举的字符串多出的部分添加到已得字符串上 
				vis[i] ++;
				dfs(tmp, sum + ssz - j);
				vis[i] --;
			}
		}
		
	}
}

int main()
{
	cin>>n;
	for(int i = 1;i <= n;i ++) cin>>s[i];
	cin>>ch;
	
	for(int i = 1;i <= n;i ++) {
		if(s[i][0] == ch) {
			vis[i] ++;
			dfs(s[i], s[i].size());
			vis[i] --;
		}
	}

	cout << ans << endl;	
	return 0;
}