Concatenated Words — Trie + Word Break

Problem

Find all words that can be formed by concatenating at least two shorter words from the same list.

Approach — Trie + Word Break DP

Build trie from all words. For each word, run word break DP: dp[i]=True if s[:i] can be formed. A word is concatenated if dp[n]=True using at least 2 words.

Time: O(n * L²) | Space: O(total chars)

Solutions

Python

class Solution:
    def findAllConcatenatedWordsInADict(self, words: list[str]) -> list[str]:
        word_set=set(words)
        def canForm(w):
            if not w: return False
            n=len(w); dp=[False]*(n+1); dp[0]=True
            for i in range(1,n+1):
                for j in range(i):
                    if dp[j] and w[j:i] in word_set and (j>0 or i<n):
                        dp[i]=True; break
            return dp[n]
        return [w for w in words if canForm(w)]

Complexity

Time: O(n * L²) | Space: O(n * L)