💬 Discord
Sign In
NeetCode #671LC-139Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#671 · #139 · Word Break(单词拆分)

📌 Problem Statement & Constraints

Given a string s and a dictionary wordDict, return whether s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused. Constraints: 1 <= s.length <= 300, 1 <= wordDict.length <= 1000, 1 <= wordDict[i].length <= 20.

💡 Core Algorithmic Approaches

  1. Let dp[i] indicate whether the prefix s[:i] can be segmented, with dp[0] = true for the empty prefix.
  2. For each i, try every split point j < i: if dp[j] is true and s[j:i] is a dictionary word, then dp[i] becomes true.
  3. Put the dictionary into a set so membership tests are O(1) on average.
  4. The answer is dp[n].

💻 Benchmark Python3 Implementation

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break              # this prefix is already reachable
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2) substring checks, each O(L) to build and hash; with n <= 300 this is fast.
💾 Space Complexity
O(n) for the DP array plus the word set.

⚠️ Interview Pitfalls & Follow-ups

  • Using a greedy longest-match scan: for s = cars with words car, ca, rs, greedy takes car and then cannot cover the trailing s, while ca + rs succeeds.
  • Forgetting dp[0] = True: without the empty prefix, no segmentation can ever start.
  • Using a list for the dictionary: membership becomes a linear scan of all words; a set is required for speed.
  • Breaking before setting dp[i]: the break must come after the assignment, otherwise the reachable prefix is discarded.