Word Break and Partition Problems: DP on Prefixes

When a coding interview question asks you to split a string into valid dictionary words or palindromes, stop writing exponential backtracking loops and define your array state over prefixes instead. By letting dp[i] represent whether the prefix of length i can be segmented, you turn an exponential search into a clean linear scan that passes every test case on DSA Tracker.

The Prefix State Definition

String problems break when you try to track where you are inside the middle of the word. Instead, anchor every state at the end of a prefix. If you have a string of length n, create a boolean array dp of size n + 1 where index i corresponds to the substring from index 0 to i - 1.

For the input string s = "leetcode" and a dictionary containing ["leet", "code"], dp[4] is true because the prefix leet of length 4 exists in the dictionary. Then dp[8] becomes true because dp[4] is true and the remaining substring code also exists in the dictionary. The base case is always dp[0] = true to anchor the empty prefix.

Transforming Backtracking into DP

Start with a recursive function that tries every possible split point. If you memoize that recursion with a lookup table, you are essentially building a dynamic programming table from left to right.

Take s = "aab" with dictionary ["a", "b"]. A naive recursive function checks "a" and recurses on "ab", then checks "aa" and recurses on "b". Without memoization, this recalculates "ab" multiple times. With an array dp where dp[i] checks all valid previous cut points j from 0 to i - 1, you compute each prefix exactly once. The outer loop runs from i = 1 to n, and the inner loop checks every valid split point j.

Palindrome Partitioning Minimum Cuts

The exact same prefix logic solves minimum cut problems by changing what you store in the table. For s = "ababbbabbababa", finding the fewest cuts to make every substring a palindrome requires an auxiliary table for palindrome checks combined with a dp array storing integer cut counts instead of booleans.

Let dp[i] be the minimum cuts needed for the prefix of length i. If the entire prefix s[0...i-1] is a palindrome, dp[i] = 0. Otherwise, loop through every split point j from 0 to i - 1. If the suffix s[j...i-1] is a palindrome, update dp[i] to the minimum of its current value and dp[j] + 1. This prevents redundant work and keeps the time complexity at O(n^2) when precomputing the palindrome table.

Decode Ways and Edge Cases

Decode ways uses the exact same prefix structure with two choices at each step. For s = "226", dp[i] stores the number of ways to decode the prefix of length i.

When evaluating index i, check two things independently. If the single digit s[i-1] is between 1 and 9, add dp[i-1] to your total. If the two-digit combination s[i-2...i-1] falls between 10 and 26, add dp[i-2] as well. Always size your dp array to n + 1 to handle single-character lookups without writing out-of-bounds protection for index -1.

Implementation Rules to Memorize

Here is the exact pattern to write down during a whiteboard round or an online assessment.

• Define dp[i] as the property of the prefix ending at index i - 1.
• Set dp[0] to the identity value, such as true for boolean checks or 0 for cost counts.
• Run an outer loop i from 1 to n to build the solution progressively.
• Run an inner loop j from 0 to i - 1 to test all possible last segments.
• Return dp[n] as the final answer for the full string.

Run through the Word Break module on DSA Tracker today and write out the prefix indices by hand before typing code.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search trees on Wikipedia.