Skip to content
Tutorials Center
My learning

Topics

Lesson 156 of 225 ยท Dynamic Programming

DP on Strings

Solve classic string DP problems in Python: palindromic subsequence, palindrome cuts, word break, wildcard and regex matching, and interleaving.

Strings are sequences, and sequences are made for dynamic programming. The state is almost always a prefix (s[:i]), a pair of prefixes (two strings), or a range (s[i..j]). The previous lesson used pairs of prefixes for LCS and edit distance. This lesson adds five more problems that show how the choice of state changes everything:

  1. Longest palindromic subsequence (range state)
  2. Palindrome partitioning, minimum cuts (prefix state plus a palindrome table)
  3. Word break (prefix state with a dictionary)
  4. Wildcard matching with ? and * (two prefixes)
  5. Regular-expression matching with . and *, and interleaving strings

For each one, start by asking "what is the smallest question I can ask about a piece of the string?"

Longest palindromic subsequence

A palindrome reads the same forwards and backwards. The longest palindromic subsequence of "bbbab" is "bbbb" (length 4); characters may be skipped.

State. dp[i][j] = length of the longest palindromic subsequence inside s[i..j] (inclusive).

Transition.

TEXT
if s[i] == s[j]:  dp[i][j] = dp[i+1][j-1] + 2     (both ends join the palindrome)
else:             dp[i][j] = max(dp[i+1][j], dp[i][j-1])   (drop one end)
dp[i][i] = 1      (a single character)

Because dp[i][j] needs rows with a larger i, fill i from the end of the string down to 0, and j from i upward.

A neat shortcut: the longest palindromic subsequence of s equals the LCS of s and its reverse.

Python Longest palindromic subsequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time and space are O(n^2). When j = i + 1 and the two characters match, dp[i+1][j-1] is dp[i+1][i], an empty range that stays 0 in the table, so the result is 2 as it should be.

Palindrome partitioning (minimum cuts)

Problem. Cut a string into pieces so that every piece is a palindrome. What is the fewest cuts? For "aab" the answer is 1 ("aa" | "b").

Step 1: know which substrings are palindromes. Build is_pal[i][j] once, using the same idea as above: s[i..j] is a palindrome if s[i] == s[j] and the inside s[i+1..j-1] is a palindrome (or empty).

Step 2: cuts by prefix. cuts[j] = the minimum cuts for the prefix ending at j. If the whole prefix is a palindrome it needs 0 cuts; otherwise try every split point i where s[i..j] is a palindrome: cuts[j] = min(cuts[i-1] + 1).

Without the palindrome table you would re-check substrings repeatedly and pay O(n^3). With it, the total is O(n^2) time and space.

Python Minimum palindrome cuts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Word break

Problem. Given a string and a dictionary of words, can the string be split into a sequence of dictionary words? For "applepenapple" and ["apple", "pen"] the answer is yes.

Brute force. Try every first word, recurse on the rest. Without memoization this is exponential, for example for "aaaaaaaab" with words ["a", "aa", "aaa"].

State. dp[i] = True if the first i characters can be segmented. dp[0] = True (the empty prefix).

Transition. dp[i] is True if there is some j < i where dp[j] is True and s[j:i] is in the dictionary.

TEXT
s = "leetcode", words = {"leet", "code"}
i:      0     1  2  3  4     5  6  7  8
dp:   True    F  F  F  True  F  F  F  True
                         ^ s[0:4] = "leet"       ^ s[4:8] = "code"

Put the words in a set for O(1) lookups. The cost is O(n^2) substring checks, or O(n x L) if you only look back as far as the longest word length L.

Python Word break and one segmentation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Wildcard matching

Problem. Pattern characters: ? matches any single character, * matches any sequence (including empty). Does the pattern match the whole string?

State. dp[i][j] = True if the first i characters of s match the first j characters of pattern p.

Transition.

TEXT
p[j-1] is '*':   dp[i][j] = dp[i][j-1]        (star matches nothing)
                         or dp[i-1][j]        (star eats one more character of s)
p[j-1] is '?' or equals s[i-1]:   dp[i][j] = dp[i-1][j-1]
otherwise:       dp[i][j] = False
dp[0][0] = True;  dp[0][j] = True only if p[:j] is all stars
Python Wildcard matching

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Regular-expression matching

Problem. Now the pattern has . (any one character) and x* meaning zero or more of the preceding character x. Match the whole string.

The star is attached to the character before it, so look two characters back in the pattern:

TEXT
if p[j-1] == '*':
    # zero copies of the preceding element
    dp[i][j] = dp[i][j-2]
    # or one more copy, if the element matches s[i-1]
    if p[j-2] == '.' or p[j-2] == s[i-1]:
        dp[i][j] = dp[i][j] or dp[i-1][j]
elif p[j-1] == '.' or p[j-1] == s[i-1]:
    dp[i][j] = dp[i-1][j-1]

The dp[i-1][j] case keeps j in place, which means "the starred element stays available for more characters".

Python Regular-expression matching with . and *

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Interleaving strings

Problem. Is s3 formed by interleaving s1 and s2, keeping the order of characters inside each? For "aabcc" and "dbbca", "aadbbcbcac" works.

State. dp[i][j] = True if s3[:i+j] can be formed from s1[:i] and s2[:j]. The next character of s3 must come from either string:

TEXT
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1])
        or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

If len(s1) + len(s2) != len(s3), answer False immediately.

Python Interleaving strings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How to pick the state for a string problem

Question about the string Typical state Typical cost
Best result for a prefix (can it be split, minimum cuts) dp[i] over prefixes O(n) to O(n^2)
Compare two strings (match, interleave, align) dp[i][j] over two prefixes O(m x n)
Property of every substring (palindrome, best inside a range) dp[i][j] over a range O(n^2)

Always write the state in a sentence first ("the first i characters of s match the first j of p"), then the transition falls out of the last character.

Common mistakes

  • Off-by-one between prefix length and index. dp[i] is about s[:i], so the last character is s[i-1].
  • Filling a range table in the wrong order. dp[i][j] often needs dp[i+1][...], so loop i downward.
  • Treating * in regex like * in wildcards. In regex it is tied to the preceding element.
  • Forgetting the empty-prefix row (for example a*b* matching the empty string).
  • Slicing inside hot loops. s[j:i] creates a new string each time; limit lookback with the longest word length.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the length of the longest palindromic subsequence of 'cbbd'?

    The subsequence 'bb' has length 2. No palindromic subsequence of length 3 exists in 'cbbd'.
  2. 2. In word break, what does dp[i] mean?

    dp[0] is True for the empty prefix. dp[i] is True when some earlier cut j has dp[j] True and s[j:i] is a word.
  3. 3. Why is a palindrome table built before computing the minimum cuts?

    Without the table every candidate piece costs O(length) to check, which gives O(n^3) overall. The table makes the total O(n^2).
  4. 4. In regex matching with 'x*', what does the transition dp[i][j] = dp[i][j-2] represent?

    Jumping back two pattern positions skips both the element and its star, meaning zero occurrences.
  5. 5. For wildcard matching, what is dp[0][j] when p[:j] contains a letter that is not '*'?

    An empty string can only be matched by a pattern made entirely of stars.

Summary

  • Pick the state as a prefix, a pair of prefixes, or a range, and say it in a sentence before coding.
  • Longest palindromic subsequence: range DP; equal ends add 2, otherwise drop one end. It equals LCS with the reverse.
  • Min palindrome cuts: precompute a palindrome table, then a prefix DP; O(n^2).
  • Word break: dp[i] is True when a True dp[j] is followed by a dictionary word; use a set and limit lookback.
  • Wildcard and regex matching use two-prefix tables; regex * binds to the previous element.
  • Interleaving: the next character of s3 must come from s1 or s2.

Next: Interval and Matrix-Chain DP