Word Break
Decide whether a string can be split into a sequence of dictionary words. dp[i] is reachable if some earlier reachable point dp[j] is followed by a dictionary word s[j..i].
- Category
- Dynamic Programming
- Time complexity
- O(n²)
- Space complexity
- O(n)
Pseudocode
dp[0] = true dp[i] = any j with dp[j] and s[j..i] in dictionary
Reference implementation
dp[0] = True
for i in range(1, n+1):
dp[i] = any(dp[j] and s[j:i] in words
for j in range(i))