Word Break Problem
- dp[i] = True if s[:i] can be formed from dictionary words.
- dp[0] = True (empty string is trivially segmentable — base case).
- Use a set for O(1) dictionary lookup instead of list for O(n) lookup.
Given a string s and a dictionary, determine if s can be segmented into dictionary words. Use dynamic programming: dp[i] = True if s[:i] can be segmented. For each i, check all j < i — if dp[j] is True and s[j:i] is in the dictionary, then dp[i] = True. Time: O(n² * m) where m is average word length.
DP Solution — Can String Be Segmented?
# Package: io.thecodeforge.python.dsa def word_break(s, word_dict): word_set = set(word_dict) # O(1) lookup n = len(s) dp = [False] * (n + 1) dp[0] = True # empty string can always be segmented for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break # found a valid split — no need to check more j values return dp[n] print(word_break('leetcode', ['leet', 'code'])) # True print(word_break('applepenapple', ['apple', 'pen'])) # True print(word_break('catsandog', ['cats', 'dog', 'sand', 'and', 'cat'])) # False
True
False
Return All Valid Segmentations
from functools import lru_cache def word_break_all(s, word_dict): word_set = set(word_dict) @lru_cache(maxsize=None) def dp(start): if start == len(s): return [[]] # empty path — base case results = [] for end in range(start + 1, len(s) + 1): word = s[start:end] if word in word_set: for rest in dp(end): results.append([word] + rest) return results return [' '.join(words) for words in dp(0)] print(word_break_all('catsanddog', ['cat', 'cats', 'and', 'sand', 'dog'])) # ['cat sand dog', 'cats and dog']
🎯 Key Takeaways
- dp[i] = True if s[:i] can be formed from dictionary words.
- dp[0] = True (empty string is trivially segmentable — base case).
- Use a set for O(1) dictionary lookup instead of list for O(n) lookup.
- For all segmentations, use memoised recursion — exponential results without memoization.
- Time: O(n²) for the check; Space: O(n) for the DP array.
Interview Questions on This Topic
- QExplain the DP recurrence for the word break problem.
- QWhat is the time complexity of the word break DP solution?
- QHow would you modify word break to return all possible segmentations?
Frequently Asked Questions
Why is the DP array of size n+1?
dp[i] represents whether the first i characters of s can be segmented — dp[0] corresponds to the empty string. Using size n+1 avoids off-by-one errors and lets dp[n] cleanly represent the full string.
Can this be solved with BFS?
Yes. Start from index 0, and for each position in the queue, try all dictionary words that start at that position. If word ends at index j, add j to the queue if not already visited. Reach n means success. BFS and DP have the same time complexity here.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.