472.md

472. Concatenated Words

Solution 1

class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        ans = []
        pre_words = set([])
        words.sort(key=lambda x: len(x))

        def check(word):
            if not pre_words:
                return False
            dp = [False for _ in range(len(word) + 1)]
            dp[0] = True
            for i in range(len(word) + 1):
                for j in range(i):
                    if dp[j] and word[j: i] in pre_words:
                        dp[i] = True
                        break
            return dp[-1]

        for word in words:
            if check(word):
                ans.append(word)
            pre_words.add(word)
        return ans