编写题解 1614: 蓝桥杯算法训练VIP-单词接龙

解题思路 n较小，可以使用dfs

注意事项: 由于第一个测试用例有问题，所有的输入数据末尾都加上了一个空格，可以把第五行的input()改为''.join(input().split())，就可以ac了。

参考代码:

n = int(input())
a = []
for _ in range(n):
   a.append(input())  # 改为''.join(input().split())

fir = input() #  改为''.join(input().split())

vis = [0 for _ in range(n)]


def check(s1, s2):  # 计算相同字母的个数
   lens = min(len(s1), len(s2))
   for i in range(1, lens + 1):
       if s1[-i:] == s2[:i]:
           return i
   return 0


def dfs(s):
   global Max
   Max = max(Max, len(s))
   for i in range(n):
       if vis[i] >= 2:
           continue
       vis[i] += 1
       l = check(s, a[i])
       if l > 0 and l < min(len(s), len(a[i])):  # l等于0则没有公共部分，等于最大值则是包含关系
           dfs(s[:-l] + a[i])
       vis[i] -= 1


Max = 0
for i in range(n):
   if a[i][0] == fir:
       vis[i] += 1
       dfs(a[i])
       vis[i] -= 1
print(Max)