139. Word Break
Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 41.9%
Problem Breakdown
We are asked to determine feasibility rather than construct the solution itself (unlike Word Break II). We need a boolean result: True if string s can be fully segmented into words from wordDict, otherwise False.
Inputs:
- String
s: The target text to segment (length <= 300). - List of strings
wordDict: Allowed dictionary entries (size <= 1000).
Outputs: Boolean value indicating segmentation success.
Implicit Constraints & Edge Cases:
- Reuse allowed: Words in the dict can be used multiple times (e.g., “applepenapple” -> apple, pen, apple).
- Empty segments not valid: We cannot have empty strings between words; every character must belong to a word.
- Partial matches don’t count: If
sends with characters that aren’t part of any dictionary word starting from the last split point, it fails immediately for that path. - Set vs List: Converting
wordDictto a set is critical for lookup time during checks.
Intuition
A naive approach would be recursion: try splitting at every possible index and recursively check if both parts are valid words or further segments of the dictionary.
Why Brute Force Fails:
This leads to an exponential explosion, roughly . For example, with s = "aaaaa" and dict containing "aa", we have many overlapping subproblems (checking if index 0-5 is valid vs checking index 1-6). We recompute the same substring validity repeatedly.
Key Insight:
This exhibits optimal substructure and overlapping subproblems—hallmarks of Dynamic Programming (DP). If a prefix s[0...i] can be segmented, we don’t need to check it again later; we just store that result in an array (dp[i]).
We define dp[i] as “True” if the substring s[:i] can be successfully broken down. We iterate through each character of s, and for every position, we ask: “Can I reach this point from a previously valid split point using one word?”
Approach
- Preprocessing: Convert
wordDictto a set (word_set) for average time complexity lookups. This is non-negotiable for performance in Python due to hashing overhead on lists. - DP State Initialization: Create an array
dpof sizelen(s) + 1. Initialize all values asFalse, exceptdp[0] = True. The base case represents the empty string before any characters, which is trivially valid (length 0). - Iteration Logic:
- Iterate through each index
ifrom 1 tolen(s). This represents the end of a potential word segment. - To determine if
dp[i]can be true, we look backwards at previous indicesj < i. These represent start points where a valid segmentation ended previously (dp[j] == True). - We check if the substring between
s[j:i]exists in our set. If it does anddp[j]is true, thendp[i] = True.
- Iterate through each index
- Optimization: Since dictionary words have a maximum length of 20 (per constraints), we don’t need to scan all previous indices
j < i. We only check the last 20 characters back fromi. This keeps complexity low even if N was larger, though for N=300 it’s not strictly necessary. - Early Exit: If at any point
dp[i]becomes true (and we are iterating forward), we can stop checking other previous indices for that specific i because one valid segmentation is sufficient to make the current position reachable.
Complexity Analysis
Time Complexity: or effectively .
Where N is string length and L is max word length (bounded by 20). In a standard implementation without the explicit length limit optimization, it’s often cited as because we check substrings. With Python slicing being linear in substring length (), checking all previous indices makes it roughly proportional to N * L. Given constraints (L <= 20), this is practically linear relative to N for the purpose of interview analysis, but strictly if we consider worst-case string slicing costs.
Space Complexity: .
We use an array dp of size N. The set takes space proportional to dictionary words (). Since constraints are small (300 chars, 1000 dict entries), this fits easily within memory limits.
Solution
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# Convert list to set for O(1) lookups
word_set = set(wordDict)
n = len(s)
# dp[i] indicates if substring s[0:i] can be segmented into dictionary words
dp = [False] * (n + 1)
# Base case: empty string is valid segmentation of length 0
dp[0] = True
for i in range(1, n + 1):
# Optimization: Only check substrings ending at current index 'i'
# with lengths up to the maximum word length (20 per constraints).
# This avoids unnecessary checks on long prefixes that can't be words.
max_len = min(i, 20)
for j in range(max(0, i - max_len), i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break # Found a valid path to 'i', no need to check other splits
return dp[n]
Edge Cases Handled
- Empty String: Constraints state
s.length >= 1, so this case is not tested per problem definition, but the code handles it naturally (returns True for empty string). - No Matches Found: If no combination of words covers the string,
dp[n]remainsFalse. - Word Longer than Remaining String: The loop range
range(max(0, i - max_len), i)ensures we don’t slice beyond available characters or check lengths exceeding 20. - Dictionary with Duplicates: Converting to a set removes duplicates automatically without affecting correctness (since reuse is allowed).
- Single Character Words: The logic handles single character words correctly as
jwill be adjacent toi.