Word Break
Can s be segmented into a sequence of dictionary words? (The backtracking variant prints every segmentation.)
02
Intuition
Whether the suffix starting at i is breakable doesn't depend on how you got to i — perfect memoization target. dp[i] = true if some dictionary word starts at i and dp[i + len(word)] holds.
03
Approach
1
Naive recursion repeats suffixes
Trying every prefix word and recursing re-solves the same suffix exponentially many times.
2
DP over positions
dp[n] = True (empty suffix). Going right to left, dp[i] = any(s.startswith(w, i) and dp[i+len(w)]). Answer dp[0].
3
Printing all ways
Keep the same recursion but collect paths, memoizing suffix → list of segmentations to avoid recomputation.
04
Solution & live demo
python
▶1class Solution:
▶2 def wordBreak(self, s, wordDict):
▶3 words = set(wordDict)
▶4 n = len(s)
▶5 dp = [False] * (n + 1)
▶6 dp[n] = True
▶7 for i in range(n - 1, -1, -1):
▶8 for j in range(i + 1, n + 1):
▶9 if s[i:j] in words and dp[j]:
▶10 dp[i] = True
▶11 break
▶12 return dp[0]
05
Edge cases
Word reuse, e.g. "aaaa" with ["a","aa"]
Dictionary words are reusable — dp naturally allows it.
s breakable only by overlapping choices, "applepenapple"
dp explores every word start, not just greedy longest.
06
Complexity
Time
O(n² · L)
Space
O(n)
L = average word slice cost; set lookup O(1).