⚡Flashcard Drill➔
NeetCode #699LC-472Hard1-D Dynamic Programming
← Back to All Problems

#699 · #472 · Concatenated Words(连接词)

📌 Problem Statement & Constraints

Given an array of distinct strings words, return all words that can be formed by concatenating at least two shorter words from the array. Constraints: 1 <= words.length <= 10^4, 1 <= words[i].length <= 30, and the total number of characters is at most 10^5.

💡 Core Algorithmic Approaches

  1. Sort the words by length so that every potential component is available before the word that uses it.
  2. Insert each word into a hash set; a word is valid if it can be segmented into at least two parts, each already in the set.
  3. For a candidate word, run a word-break DP where dp[i] is true when the prefix of length i splits into known words.
  4. Adding a word to the set only after testing it prevents the word from matching itself as a single piece.

💻 Benchmark Python3 Implementation

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words.sort(key=len)
        known = set()
        res = []

        def can_form(w: str) -> bool:
            n = len(w)
            dp = [False] * (n + 1)
            dp[0] = True
            for i in range(n):
                if not dp[i]:
                    continue
                for j in range(i + 1, n + 1):
                    if w[i:j] in known:        # a known shorter word
                        dp[j] = True
            return dp[n]

        for w in words:
            if can_form(w):
                res.append(w)
            known.add(w)               # a word may not be built from itself
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * L^2): each word of length L costs O(L^2) substring checks, with L <= 30.
💾 Space Complexity
O(total characters) for the set.

⚠️ Interview Pitfalls & Follow-ups

  • Adding the word to the set before testing it: then the word trivially matches itself as one piece.
  • Requiring two pieces explicitly: processing words in increasing length order and adding afterwards enforces the minimum-two rule implicitly.
  • Skipping the sort: without length ordering a component may not yet be in the set when it is needed.
  • Recursing without memoisation: repeated subproblems blow up on longer words.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems