AcWing 1117. 单词接龙
原题链接
简单
作者:
皓首不倦
,
2020-08-03 16:03:56
,
所有人可见
,
阅读 448
'''
简单DFS搜索即可
'''
n = int(input())
arr = []
for _ in range(n):
arr.append(input())
start_w = input()
# 预处理每一个单词可以到的下一个单词的边
link = {arr[i]:[] for i in range(n)}
for i in range(n):
for j in range(n):
len1, len2 = len(arr[i]), len(arr[j])
for k in range(1, min(len1, len2)):
if arr[i][-k:] == arr[j][:k]:
link[arr[i]].append((arr[j], k))
max_len = [0]
from collections import Counter
def dfs(cur, c:Counter, cur_len: int, path):
#print(cur, cur_len)
path.append(cur)
flag = False
for next, overlap_len in link[cur]:
if next not in c or c[next] < 2:
flag = True
c[next] += 1
dfs(next, c, cur_len + len(next) - overlap_len, path)
c[next] -= 1
if not flag:
max_len[0] = max(max_len[0], cur_len)
path.pop(-1)
for s in arr:
if s.find(start_w) == 0:
c = Counter()
c[s] = 1
dfs(s, c, len(s), [])
print(max_len[0])