AcWing 1117. 单词接龙 python
原题链接
简单
作者:
申侠
,
2020-11-19 15:16:27
,
所有人可见
,
阅读 558
n = int(input())
m = {}
for _ in range(n):
t = input(); m[t] = 2
s = input()
ss = []
for k in m:
if s == k[:len(s)]: ss.append(k)
cnt = 0
def dfs(s):
global cnt
cnt = max(cnt, len(s))
for k in m:
if m[k]:
lk = 1;ls = len(s);com = 0
while lk < len(k) and ls:
if k[:lk] == s[ls-1:len(s)]:
com = lk; break
lk += 1; ls -= 1
if com >=1 and com < min(len(k), len(s)):
m[k] -= 1; dfs(s[:len(s)-com]+k); m[k] += 1
for s in ss:
m[s] -= 1; dfs(s); m[s] += 1
print(cnt)