Word Break
Hard · rating 1850 · Dynamic Programming, Strings
The first line contains a string s. The second line contains space-separated dictionary words. Print YES if s can be segmented into a sequence of one or more dictionary words (each usable any number of times), otherwise NO.
Constraints: 1 ≤ |s| ≤ 2000
Editorial
Approach
Let dp[i] mean "the first i characters can be segmented". It's true if some split point j has dp[j] true and the substring s[j:i] is a dictionary word. Build it left to right.
Bounding the inner loop
Only split points within the longest dictionary word of i can matter, so the inner scan is short in practice.
dp = [False] * (n + 1); dp[0] = True
for i in range(1, n + 1):
for j in range(max(0, i - maxlen), i):
if dp[j] and s[j:i] in words:
dp[i] = True; break
return dp[n]Complexity
Time: O(n·L) where L is the max word length. Space: O(n).
Related problems
- Edit Distance — Hard
- Longest Common Substring — Hard
- Longest Common Subsequence — Hard
- Longest Palindromic Substring — Hard
- 0/1 Knapsack — Hard
- Coin Change (Count Ways) — Hard