The word break problem is a classic example of dynamic programming applied to string manipulation. At its core, it asks: "Can we split this string into valid pieces?" This type of problem appears frequently in text processing, natural language processing, and parsing tasks.
The key insight is recognizing that this problem has optimal substructure - if we can segment a string up to position i, and we find a valid word from position i to position j, then we can segment up to position j. This allows us to build up solutions to larger problems from solutions to smaller ones.
Why Dynamic Programming Works Here:
A naive recursive approach would check every possible way to split the string, leading to exponential time complexity. For a string of length n, there could be 2^n possible ways to split it! Dynamic programming eliminates this redundancy by storing the results of subproblems.
The typical approach uses a boolean array dp where dp[i] represents whether the substring from the start up to position i can be segmented. We fill this array incrementally, and each new position only needs to check if there's a valid word ending at that position and a valid segmentation before that word begins.
The State Transition:
For each position i, we ask: "Is there some earlier position j such that:
j can be segmented (dp[j] is true)j to i forms a valid word"This approach transforms an exponential problem into a polynomial one - typically O(n² × m) where n is string length and m is average word length.
1def can_partition_sum(nums, target):
2 """Example: Can we partition numbers to reach target sum?"""
3 dp = [False] * (target + 1)
4 dp[0] = True # Base case: sum of 0 is always possible
5
6 for num in nums:
7 # Traverse backwards to avoid using same number twice
8 for j in range(target, num - 1, -1):
9 if dp[j - num]: # If (target - num) was achievable
10 dp[j] = True # Then target is achievable
11
12 return dp[target]