472. Concatenated Words
https://leetcode.com/problems/concatenated-words/
solution
dfs [超时]
# https://zhuanlan.zhihu.com/p/134658803
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
words.sort(key=len)
prev = set()
res = []
for word in words:
if self.dfs(prev, word):
res.append(word)
prev.add(word)
return res
def dfs(self, prev, word):
if not prev:
return False
if not word:
return True
for i in range(1, len(word)+1):
if word[:i] in prev and self.dfs(prev, word[i:]):
return True
return False
时间复杂度:O() 空间复杂度:O()
动态规划
trie
follow up
返回所有结果
Last updated