Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import copy
T = int(input())
def calc_min_len(ws):
min_len = 999999
for w in ws:
l = len(w)
if l < min_len:
min_len = l
return min_len
def check_words_clear(words):
for w in words:
if w != "":
return True
return False
def find_rhyme(words, used_suffix, num, min_len):
#print("find_rhyme", num, min_len, words)
if num > min_len:
return 0
if not(check_words_clear(words)):
return 0
lengths = [0]
for i in range(len(words)):
if words[i] == "" or words[i][-num:] in used_suffix:
continue
for j in range(i+1, len(words)):
if words[j] == "":
continue
if words[i][-num:] == words[j][-num:]:
#print("use", words[i], words[j])
words2 = copy.deepcopy(words)
used_suffix2 = copy.deepcopy(used_suffix)
used_suffix2.append(words[i][-num:])
words2[i] = ""
words2[j] = ""
len2 = 2 + find_rhyme(words2, used_suffix2, num, min_len)
len2 += find_rhyme(words2, used_suffix2, num+1, min_len)
lengths.append(len2)
return max(lengths)
for cnt in range(T):
N = int(input())
words = [input() for _ in range(N)]
print("Case #"+str(cnt+1)+":", str(find_rhyme(words, [], 1, calc_min_len(words))))
@showyou

This comment has been minimized.

Copy link
Owner Author

commented Apr 13, 2019

Sampleは通りましたがWAです

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.