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
- Sort the words by length so that every potential component is available before the word that uses it.
- 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.
- For a candidate word, run a word-break DP where
dp[i]is true when the prefix of lengthisplits into known words. - 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.