NeetCode #521LC-140HardBacktrackingNC 250
← Back to All Problems#521 · #140 · Word Break II(单词拆分 II)
📌 Problem Statement & Constraints
Given a string
s and a dictionary wordDict, add spaces to construct sentences where every word is in the dictionary. Return all such sentences in any order. Words may be reused. Constraints: 1 <= s.length <= 20, 1 <= wordDict.length <= 1000, word lengths up to 10.💡 Core Algorithmic Approaches
- This is Word Break with the actual sentences returned, so memoise the suffix results.
dfs(i)returns all valid sentences formed froms[i:]; the base casei == nreturns[""].- For each dictionary word matching at
i, prepend it to every sentence fromdfs(i + len(w)). - Memoisation is essential: without it, the same suffix is recomputed exponentially many times.
💻 Benchmark Python3 Implementation
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
words = set(wordDict)
n = len(s)
memo = {}
def dfs(i: int) -> List[str]:
if i == n:
return [""] # one empty completion
if i in memo:
return memo[i]
res = []
for j in range(i + 1, n + 1):
w = s[i:j]
if w in words:
for tail in dfs(j):
res.append(w + (" " + tail if tail else ""))
memo[i] = res
return res
return dfs(0)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 * 2^n) worst case, since the output itself can be exponential in size.
💾 Space Complexity
O(n * 2^n) for the memo table in the worst case.
⚠️ Interview Pitfalls & Follow-ups
- Not memoising: exponential repeated work on suffixes.
- Returning
[]for the base case instead of[""]: the concatenation loop would produce nothing. - Joining with a space unconditionally: the final word must not have a trailing space, hence the conditional join.
- Assuming a single solution: there can be exponentially many.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.