Word Break and Segment String
Use a 1D DP table to determine if a string can be segmented into dictionary words, analysing the O(n²) time and why a trie speeds it up.
The Word Break Problem
Word Break (LeetCode 139) asks: given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, with s = 'leetcode' and wordDict = ['leet', 'code'], the answer is True because 'leet' + 'code' = 'leetcode'. This is a classic 1D DP problem.
s = 'leetcode'
word_set = {'leet', 'code'}
# Can we split 'leetcode' into words from word_set?
# 'leet' in set → yes, 'code' in set → yes
# So: 'leetcode' = 'leet' + 'code' → True
s2 = 'catsandog'
word_set2 = {'cats', 'dog', 'sand', 'and', 'cat'}
# No matter how we split, last part 'og' not in dict
print('Expected: True, False')DP Formulation and State
Define dp[i] as True if the substring s[:i] can be segmented using the dictionary. The base case is dp[0] = True (the empty string is always segmentable). For each position i, check all positions j < i: if dp[j] is True and s[j:i] is in the dictionary, then dp[i] = True. The final answer is dp[len(s)].
def word_break(s, word_dict):
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # empty string
for i in range(1, n + 1):
for j in range(i):
# If s[:j] is segmentable AND s[j:i] is a word
if dp[j] and s[j:i] in word_set:
dp[i] = True
break # no need to check other j values
return dp[n]
print(word_break('leetcode', ['leet', 'code'])) # True
print(word_break('catsandog', ['cats','dog','sand','and','cat'])) # FalseAll lessons in this course
- House Robber: Take-or-Skip Recurrence
- Maximum Subarray and Maximum Product Subarray
- Word Break and Segment String
- Decode Ways and Counting Paths