472 - Concatenated Words
Written on January 20, 2020
Tweet
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
if not words:
return []
words_set = set(words)
def dfs(word):
for i in range(1, len(word)):
prefix = word[:i]
suffix = word[i:]
if prefix in words_set and suffix in words_set:
return True
elif prefix in words_set and dfs(suffix):
return True
return False
return [w for w in words if dfs(w)]