菜鸟的每日力扣系列——472. 连接词

from typing import List

def findAllConcatenatedWordsInADict(words: List[str]) -> List[str]:
    words.sort(key=len)  # 原地排序
    min_len = max(1, len(words[0]))  # 设置初始值为首个字符串长度
    prev: set = set()  # 用集合去重
    res: list = []
    
    def check(word):
        if word in prev:
            return True
        for i in range(min_len, len(word) + 1):
            if word[:i] in prev and check(word[i:]):
                return True
        return False
        
    for word in words:
        if check(word):
            res.append(word)
        prev.add(word)
    return res

words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
print(findAllConcatenatedWordsInADict(words))
#结果是：['dogcatsdog', 'catsdogcats', 'ratcatdogcat']

words= ['cat', 'dog', 'rat', 'cats', 'dogcatsdog', 'catsdogcats', 'ratcatdogcat', 'hippopotamuses']
word= cat
i= 3 word[:i]= cat word[i:]= 
prev= {'cat'}
word= dog
i= 3 word[:i]= dog word[i:]= 
prev= {'dog', 'cat'}
word= rat
i= 3 word[:i]= rat word[i:]= 
prev= {'dog', 'rat', 'cat'}
word= cats
i= 3 word[:i]= cat word[i:]= s
word= s
i= 4 word[:i]= cats word[i:]= 
prev= {'dog', 'rat', 'cats', 'cat'}
word= dogcatsdog
i= 3 word[:i]= dog word[i:]= catsdog
word= catsdog
i= 3 word[:i]= cat word[i:]= sdog
word= sdog
i= 3 word[:i]= sdo word[i:]= g
i= 4 word[:i]= sdog word[i:]= 
i= 4 word[:i]= cats word[i:]= dog
word= dog
res= ['dogcatsdog']
prev= {'dog', 'cat', 'rat', 'cats', 'dogcatsdog'}
word= catsdogcats
i= 3 word[:i]= cat word[i:]= sdogcats
word= sdogcats
i= 3 word[:i]= sdo word[i:]= gcats
i= 4 word[:i]= sdog word[i:]= cats
i= 5 word[:i]= sdogc word[i:]= ats
i= 6 word[:i]= sdogca word[i:]= ts
i= 7 word[:i]= sdogcat word[i:]= s
i= 8 word[:i]= sdogcats word[i:]= 
i= 4 word[:i]= cats word[i:]= dogcats
word= dogcats
i= 3 word[:i]= dog word[i:]= cats
word= cats
res= ['dogcatsdog', 'catsdogcats']
prev= {'catsdogcats', 'dog', 'cat', 'rat', 'cats', 'dogcatsdog'}
word= ratcatdogcat
i= 3 word[:i]= rat word[i:]= catdogcat
word= catdogcat
i= 3 word[:i]= cat word[i:]= dogcat
word= dogcat
i= 3 word[:i]= dog word[i:]= cat
word= cat
res= ['dogcatsdog', 'catsdogcats', 'ratcatdogcat']
prev= {'catsdogcats', 'dog', 'cat', 'rat', 'cats', 'ratcatdogcat', 'dogcatsdog'}
word= hippopotamuses
i= 3 word[:i]= hip word[i:]= popotamuses
i= 4 word[:i]= hipp word[i:]= opotamuses
i= 5 word[:i]= hippo word[i:]= potamuses
i= 6 word[:i]= hippop word[i:]= otamuses
i= 7 word[:i]= hippopo word[i:]= tamuses
i= 8 word[:i]= hippopot word[i:]= amuses
i= 9 word[:i]= hippopota word[i:]= muses
i= 10 word[:i]= hippopotam word[i:]= uses
i= 11 word[:i]= hippopotamu word[i:]= ses
i= 12 word[:i]= hippopotamus word[i:]= es
i= 13 word[:i]= hippopotamuse word[i:]= s
i= 14 word[:i]= hippopotamuses word[i:]= 
prev= {'catsdogcats', 'dog', 'cat', 'rat', 'cats', 'ratcatdogcat', 'dogcatsdog', 'hippopotamuses'}
['dogcatsdog', 'catsdogcats', 'ratcatdogcat']