⚡Flashcard Drill➔
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

  1. This is Word Break with the actual sentences returned, so memoise the suffix results.
  2. dfs(i) returns all valid sentences formed from s[i:]; the base case i == n returns [""].
  3. For each dictionary word matching at i, prepend it to every sentence from dfs(i + len(w)).
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems