472. Concatenated Words

leverage 139. Word Break
Time complexity is O(N * L^3) where N is number of words and L is length of each word

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)
        output = []
        for word in words:
            wordSet.remove(word)
            if self.isConcatenatedWord(word, wordSet):
                output.append(word)
            wordSet.add(word)
        return output
        
    
    def isConcatenatedWord(self, word: str, wordSet: Set[str]) -> bool:
        if len(word) <= 0:
            return False
        
        cache = [False for _ in range(len(word)+1)]
        cache[0] = True
        
        for i in range(len(word)+1):
            for j in range(i+1, len(word)+1):
                if cache[i] and word[i:j] in wordSet:
                    cache[j] = True
        return cache[len(word)]

472. Concatenated Words - cocoder39/coco39_LC GitHub Wiki