class Solution:
    def cat(self, word, words, record):
        if word in record:
            return record[word]
        result = False
        for i in range(len(word)):
            if word[:i+1] in words:
                next = word[i+1:]
                result = (next in words) or (self.cat(next, words, record))
                if result:
                    break
        record[word] = result
        return result

    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words = set(words)
        ans = []
        record = {}
        for word in words:
            if self.cat(word, words, record):
                ans.append(word)
        return ans


나는 릿코드를 믿었다!

트라이 같은 고급 테크닉을 요구할 리가 없어!

세상은 브루트포스가 지배한다 (=시간복잡도 계산 안 함)