MediumBlind75StringDPHash Table
Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Examples
Input
s = 'leetcode', wordDict = ["leet","code"]
Output
true
Return true because 'leetcode' can be segmented as 'leet code'.
Input
s = 'catsandog', wordDict = ["cats","dog","sand","and","cat"]
Output
false
No valid segmentation exists.
Constraints
- •
1 <= s.length <= 300 - •
1 <= wordDict.length <= 1000 - •
1 <= wordDict[i].length <= 20 - •
s and wordDict[i] consist of only lowercase English letters. - •
All the strings of wordDict are unique.
Approaches
Try all possible segmentations recursively.
CodeT: O(2^n) | S: O(n)
def word_break(s, wordDict):
word_set = set(wordDict)
def helper(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and helper(end):
return True
return False
return helper(0)Use DP where dp[i] is True if s[:i] can be segmented.
CodeT: O(n^2 * k) | S: O(n)
def word_break(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]Same DP with early termination.
Diagram
s = 'leetcode', wordDict = ['leet','code']
dp[0]=True
i=4: s[0:4]='leet' in dict, dp[4]=True
i=8: s[4:8]='code' in dict and dp[4]=True, dp[8]=True
Result: True
CodeT: O(n * max_len) | S: O(n)
def word_break(s, wordDict):
word_set = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
max_len = max(len(w) for w in wordDict) if wordDict else 0
for i in range(1, n + 1):
for j in range(max(0, i - max_len), i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^n) | O(n) | Try all possible segmentations recursively. |
| DP - Bottom Up | O(n^2 * k) | O(n) | Use DP where dp[i] is True if s[:i] can be segmented. |
| Optimized DP | O(n * max_len) | O(n) | Same DP with early termination. |
Recursion
T: O(2^n)S: O(n)
Try all possible segmentations recursively.
DP - Bottom Up
T: O(n^2 * k)S: O(n)
Use DP where dp[i] is True if s[:i] can be segmented.
Optimized DP
T: O(n * max_len)S: O(n)
Same DP with early termination.
Common Mistakes
Using recursion without memoization
Not using a set for O(1) word lookup
Checking all words at each position instead of all positions for each word