LeetCode 472: Concatenated Words Solution in Python – A Step-by-Step Guide

What Is LeetCode 472: Concatenated Words?

In LeetCode 472: Concatenated Words, you’re given a list of strings words, and your task is to find all words that can be formed by concatenating two or more other words from the list (excluding itself as a single unit). For example, in ["cat", "dog", "catdog"], "catdog" is a concatenated word (cat + dog). Each word used in the concatenation must be in the list, and the result must use at least two words. It’s like piecing together a word puzzle where the pieces are the words themselves.

Problem Statement

• Input: words (List[str])—list of strings.
• Output: List[str]—all concatenated words.
• Rules:
• Word must be formed by 2+ other words from the list.
• Cannot use the word itself as a single concatenation.
• Each word in concatenation must be in words.

Constraints

• 1 <= words.length <= 10^4.
• 1 <= words[i].length <= 30.
• words[i] consists of lowercase English letters.
• All words are unique.

Examples to Get Us Started

• Input: words = ["cat","cats","catsdog","dog","rat","catdog"]
• Output: ["catsdog","catdog"] ("catsdog" = cats + dog, "catdog" = cat + dog).
• Input: words = ["cat","dog","catdog"]
• Output: ["catdog"] ("catdog" = cat + dog).
• Input: words = ["cat","dog"]
• Output: [] (No concatenations).

Understanding the Problem: Piecing the Puzzle

To solve LeetCode 472: Concatenated Words in Python, we need to identify words in the list that can be split into two or more smaller words, all present in the list. A naive approach—checking all splits recursively—could be O(2^n) per word, slow for 10^4 words. The key? Use a Trie for fast prefix lookup and dynamic programming to efficiently validate concatenations. We’ll explore:

• Best Solution (DP with Trie Optimization): O(n * L^2) time, O(n * L) space—fast and optimal (n = word count, L = max word length).
• Alternative Solution (Brute Force Recursion): O(n * 2^L) time, O(L) space—simple but inefficient.

Let’s dive into the Trie + DP solution—it’s the detective’s word-weaving toolkit we need.

Best Solution: Dynamic Programming with Trie Optimization

Why This Is the Best Solution

The DP with Trie optimization is the top pick because it’s O(n * L^2) time and O(n * L) space, efficiently finding concatenated words by using a Trie for O(1) prefix lookups and DP to check splits in O(L^2) per word. It avoids redundant checks by leveraging word set lookups and memoized splits. It’s like building a word dictionary tree and tracing puzzle pieces through it—smart and swift!

How It Works

Here’s the strategy:

• Step 1: Build a set of words (excluding current word during check).
• Step 2: Define is_concat(word, start, word_set, memo):
• Check if word[start:] can be split into 2+ words from word_set.
• Memoize results for each start position.
• Step 3: For each word:
• Use DP to test if it’s concatenated (at least 2 parts).
• Add to result if True.
• Step 4: Return list of concatenated words.
• Why It Works:
• Trie or set ensures O(1) word lookup.
• DP reduces split checks to O(L^2) per word.

Step-by-Step Example

Example: words = ["cat", "dog", "catdog"]

• Word Set: {"cat", "dog", "catdog"}.
• Check "cat":
• "cat": No split into 2+, False.
• Check "dog": False.
• Check "catdog":
• Exclude "catdog", set = {"cat", "dog"}.
• Start=0: "catdog":
• Split at 3: "cat" (in set), "dog" (in set), True (2 parts).
• Result: True, add "catdog".
• Result: ["catdog"].

Example: words = ["cat", "cats", "catsdog"]

• Check "catsdog":
• Set: {"cat", "cats"}.
• "catsdog":
• "cat" + "sdog" (not in set).
• "cats" + "dog" (not in set), but "cats" splits to "cat" + "s" (not in set).
• Full check: "cats" + "dog", add "dog" to set, True.
• Result: ["catsdog"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        # Step 1: Build word set
        word_set = set(words)
        result = []
        memo = {}

        # Step 2: DP helper to check if word is concatenated
        def is_concat(word, start, word_set, memo):
            if start in memo:
                return memo[start]
            if start == len(word):
                return True  # Empty string is valid end

            for i in range(start + 1, len(word) + 1):
                prefix = word[start:i]
                if prefix in word_set and is_concat(word, i, word_set, memo):
                    memo[start] = True
                    return True
            memo[start] = False
            return False

        # Step 3: Check each word
        for word in words:
            word_set.remove(word)  # Exclude self
            # Check if word can be split into 2+ parts
            for i in range(1, len(word)):
                prefix = word[:i]
                suffix = word[i:]
                if (prefix in word_set and 
                    (suffix in word_set or is_concat(suffix, 0, word_set, {}))):
                    result.append(word)
                    break
            word_set.add(word)  # Add back

        return result

• Line 4-6: Build word set, init result and memo.
• Line 9-20: is_concat:
• Base case: start at end, True.
• Check prefixes in set, recurse on suffix.
• Memoize results.
• Line 23-34: Check each word:
• Remove word, test splits for 2+ parts.
• Add to result if valid, restore set.
• Time Complexity: O(n * L^2)—n words, L^2 splits per word.
• Space Complexity: O(n * L)—set and memo.

It’s like a word-weaving sleuth!

Alternative Solution: Brute Force Recursion

Why an Alternative Approach?

The brute force recursion tries all splits—O(n * 2^L) time, O(L) space—recursively checking each substring without memoization. It’s slow but intuitive, like manually piecing together every word combo. Good for small lists or learning!

How It Works

• Step 1: Recurse on each word, try all splits.
• Step 2: Check if split parts are in word set.
• Step 3: Return concatenated words.

Step-by-Step Example

Example: words = ["cat", "dog", "catdog"]

• "catdog":
• "cat" + "dog": Both in set, True.
• Result: ["catdog"].

Code for Brute Force

Copy codeclass Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        word_set = set(words)
        result = []

        def is_concat(word, word_set, parts=0):
            if not word and parts >= 2:
                return True
            for i in range(1, len(word) + 1):
                prefix = word[:i]
                if prefix in word_set:
                    if is_concat(word[i:], word_set, parts + 1):
                        return True
            return False

        for word in words:
            word_set.remove(word)
            if is_concat(word, word_set):
                result.append(word)
            word_set.add(word)

        return result

• Line 6-15: Recurse, count parts, check splits.
• Line 17-22: Test each word, exclude self.
• Time Complexity: O(n * 2^L)—exponential splits.
• Space Complexity: O(L)—recursion stack.

It’s a slow word stitcher!

Comparing the Two Solutions

• DP with Trie (Best):
• Pros: O(n * L^2), fast, scalable.
• Cons: O(n * L) space.
• Brute Force (Alternative):
• Pros: O(n * 2^L), simple.
• Cons: Impractical for large L.

DP wins for efficiency.

Edge Cases and Examples

• Input: ["a"] → [].
• Input: ["cat"] → [].
• Input: ["a","b","ab","abc"] → ["ab","abc"].

DP handles all well.

Complexity Recap

• DP: Time O(n * L^2), Space O(n * L).
• Brute Force: Time O(n * 2^L), Space O(L).

DP’s the champ.

Key Takeaways

• DP: Optimize with memo.
• Brute Force: Check all splits.
• Python Tip: Sets speed lookups—see [Python Basics](/python/basics).

Final Thoughts: Uncover Those Words

LeetCode 472: Concatenated Words in Python is a word-weaving detective tale. DP with Trie is your fast sleuth, while brute force is a slow puzzler. Want more wordplay? Try LeetCode 139: Word Break or LeetCode 140: Word Break II. Ready to stitch some words? Head to Solve LeetCode 472 on LeetCode and detect them today—your coding skills are word-ready!