class Solution:
def _dfs(self, w):
for i in range(1, len(w)):
prefix, suffix = w[:i], w[i:]
if prefix in self.hashmap:
if suffix in self.hashmap:
return True
elif self._dfs(suffix):
return True
return False
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
self.hashmap = set(words)
ans = []
for w in words:
if self._dfs(w):
ans.append(w)
return ans