Problem statement

https://leetcode.com/problems/concatenated-words/

Solution

One way to solve this problem is to use dfs with memorization. dfs(word) will answer the quistion for given word. For this we need to check all prefixes

Complexity

Note, that we actually always call our dfs for words prefixes, so potential time complexity is O(n*m^3), where n is number of words and m is average length of word: we can have upty O(n * m) states and for each state we can make upto m checks each of which will take O(m) time. However in practice it works very fast due to python optimized strings.

Code

class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        d = set(words)
        
        @lru_cache(None)
        def dfs(word):
            for i in range(1, len(word)):
                if word[:i] in d and (word[i:] in d or dfs(word[i:])):
                    return True
            return False
        
        return [word for word in words if dfs(word)]

Remark

Another approach is to use Problem 0139 Word Break for each word in dictionary versus all others. Complexity will be also O(n * m^3), however in this case we need to do early stopping for cases like a, aa, aaa, ..., aaa...aaa.

Also it can be solved using tries: we can put all words in trie and then for each word we start to look its prefix in trie and if we found prefix equal to some word in our candidates, we have two options: continue to traverse or jump to the root of our trie, but continue to traverse word.