Concatenated Words

Intuition

Solution

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