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

题目

题目链接

题解

DFS。

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

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

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

还是觉得离谱。

代码

#include
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  1) continue;
		
		int ssz = s[i].size();
		int m = min(strsz, ssz);
		
		for(int len = 1;len s[i];
	cin>>ch;
	
	for(int i = 1;i