472. Concatenated Words
利用Trie做出一個(gè)TLE的版本斤程。其實(shí)簡單的利用recursion就可以了菩混。
class Solution(object):
def findAllConcatenatedWordsInADict(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
res = []
s = set(words)
for word in words:
s.remove(word);
if self.check(word,s):
res.append(word)
s.add(word)
return res
def check(self, word, s):
if word in s:
return True
l = len(word) - 1
while l >= 1:
if word[0:l] in s and self.check(word[l:],s):
return True
l -= 1
return False
