DP on Strings

Two-string prefix tables, regex and wildcard matching, palindromes and splitting strings.

DP on strings is the classic two-dimensional DP: compare two sequences (or one sequence with itself) and fill a table indexed by prefixes or substrings. Edit distance, longest common subsequence, regex matching and palindromes all use the same few templates. Once you can define the state precisely, the recurrences almost write themselves.

Template 1: two strings, prefix by prefix

The state is dp[i][j] = the answer for the prefixes a[:i] and b[:j]. Use an extra row and column for empty prefixes, so the base cases are explicit.

The transitions look at the last characters, a[i-1] and b[j-1]:

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

[!TIP] Draw the table For a two-string DP, sketch the grid with one string across the top and the other down the side, including the empty-prefix row and column. Fill in the first few cells by hand while you explain. It catches off-by-one errors, and it's the clearest explanation you can give.

Template 2: pattern matching

Wildcard (? matches one character, * matches any sequence):

? or the same character: dp[i][j] = dp[i-1][j-1]
*: either it matches nothing (dp[i][j-1]) or it absorbs one more character (dp[i-1][j])

Regex (. matches any character, x* matches zero or more x). * applies to the previous character:

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(2, n + 1):                     # patterns like a*b*c* match ""
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]                               # use x* zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more x
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[m][n]

Template 3: one string, substrings

The state is dp[i][j] = the answer for the substring s[i..j]. Fill it by increasing length, or loop i from the end backwards, so that shorter substrings are ready first.

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

For palindromic substrings (contiguous), you often don't need a table at all. Expand around each center (2n − 1 centers) in O(n²) time and O(1) space.

Template 4: splitting a string

The state is dp[i] = the answer for the prefix s[:i]. Try every last piece s[j:i]:

Word break: dp[i] = any(dp[j] and s[j:i] in words)
Decode ways: add dp[i-1] if the last digit is valid, and dp[i-2] if the last two digits form 10–26.
Palindrome partitioning II (minimum cuts): dp[i] = min(dp[j] + 1) over every palindromic s[j:i]. Precompute which substrings are palindromes.

Saving space

When row i only reads row i − 1, keep two rows (or one row plus a saved diagonal value). That reduces O(m × n) space to O(n). Mention it, but write the full table first unless the interviewer asks.

[!WARNING] Index alignment With a (m+1) × (n+1) table, dp[i][j] refers to the characters a[i-1] and b[j-1]. Mixing up the table index and the string index is the single most common bug in these problems. Say the convention out loud before writing the loops.

[!TIP] Practice Longest Common Subsequence · Edit Distance · Distinct Subsequences · Interleaving String · Wildcard Matching · Regular Expression Matching · Longest Palindromic Subsequence · Word Break · Decode Ways