String DP
Why this exists
A lot of everyday software asks questions about two strings at once, or about all the ways to cut one string into pieces:
- Your shell expands
*.md. Doesnotes.mdmatch? Doesa*b?cmatchaxxbyc? - A search box gets
"thequickbrownfox"with no spaces (a hashtag, a domain name, a Thai or Chinese sentence). Can it be split into dictionary words, and how? - A test framework asks whether a log line matches the regular expression
ERR.*timeout. - A biologist asks how many times the motif
bagappears as a scattered subsequence insidebabgbag.
Try any of these with plain recursion and you hit the same wall: every *, every possible cut point, every "take this letter or skip it" choice doubles the work. A 30-character string with a few stars can take millions of recursive calls. Yet the number of different questions those calls ask is tiny: "does the first i letters of the text match the first j letters of the pattern?" There are only about (m + 1) × (n + 1) such questions. String DP is the habit of answering each of those prefix questions once, in a table, and reading the answer from a corner.
This lesson builds that habit on six classic problems:
- Word break: can a string be cut into dictionary words?
- Wildcard matching:
?matches one character,*matches any run of characters. - Regex matching:
.matches one character,x*matches zero or more copies ofx. - Distinct subsequences: how many ways can
tbe picked out ofs, letter by letter, in order? - Palindrome partitioning: list all cuts of a string into palindromes, and find the fewest cuts.
- Interleaving strings: can
cbe made by shufflingaandbtogether while keeping each one's order?
You should already know what a DP state, transition and base case are, from DP Foundations. The two-string table here is the same one used for LCS and edit distance in Sequence DP; this lesson shows how far that one table shape stretches. Basic string handling (slicing, indexing, why s[j:i] costs time) is in Strings in Depth.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "can the string be segmented / split / broken into words from a list" | Word break: dp[i] = can the first i letters be split |
| "return all sentences / all segmentations" | Word break plus memoized backtracking (watch the output size) |
| "number of ways to split into words" | Word break with counts instead of booleans |
Pattern with ? and *, "glob", "file name mask" | Wildcard DP, or the greedy two-pointer with star backtracking |
Pattern with . and * where * repeats the previous character | Regex DP: treat x* as one token |
"how many times does t occur as a subsequence of s", "count the ways to delete letters to get t" | Distinct subsequences: dp[i][j] = dp[i-1][j] + (match ? dp[i-1][j-1] : 0) |
| "partition into palindromes", "every piece is a palindrome" | Palindrome table pal[i][j], then backtracking (list) or a 1D DP (min cuts) |
| "minimum cuts so each part is a palindrome / is a word / is valid" | Partition DP over cut positions, see Partition DP |
"can c be formed by merging a and b keeping relative order" | Interleaving: dp[i][j] = can c[:i+j] be built from a[:i] and b[:j] |
| Two strings, "match", "transform", "align", "common", answer lives in a corner | Two-dimensional prefix table dp[i][j] |
| One string, "cut", "split", "segment" | One-dimensional table over cut positions dp[i] |
The meta-trigger: the answer for a whole string is built from the answer for a shorter prefix (or a shorter pair of prefixes), and only the last character or the last piece decides how. When you see that, the state is "how much of each string have I consumed", and the table has one dimension per string.
Intuition & first principles
Two fingers on two strings
Picture a text written on one strip of paper and a pattern on another. Put your left finger at the start of the text and your right finger at the start of the pattern. At each moment you ask: does the part of the text before my left finger match the part of the pattern before my right finger? Moving a finger one letter to the right is a step. Some steps are forced (two plain letters must be equal), some are choices (a * can swallow one more letter, or stop).
The positions of the two fingers are the whole story. It does not matter how you got your fingers there, only where they are. That is the key insight of DP: if the future depends only on where you are and not on the path you took, you can store one answer per position. With a text of length m and a pattern of length n, the left finger has m + 1 positions (before the first letter, ..., after the last) and the right finger has n + 1. So there are (m + 1)(n + 1) states, and we keep them in a grid:
- Row
imeans "the firstiletters of the text", writtens[:i]. Row 0 is the empty prefix, written ε (the Greek letter epsilon, the usual name for the empty string). - Column
jmeans "the firstjletters of the pattern",p[:j]. - Cell
dp[i][j]stores the answer for that pair of prefixes.
flowchart LR
A["dp[i-1][j-1]<br/>both fingers one step back"] -->|"s[i-1] and p[j-1] consumed together"| D["dp[i][j]"]
B["dp[i-1][j]<br/>text finger one step back"] -->|"s[i-1] consumed, pattern stays"| D
C["dp[i][j-1]<br/>pattern finger one step back"] -->|"p[j-1] consumed, text stays"| D
Every two-string problem in this lesson fills dp[i][j] from some of these three neighbours: the diagonal (both strings advanced), up (only the text advanced) and left (only the pattern advanced). What changes between problems is which neighbours are allowed and how they combine (or for yes/no questions, + for counting, min for optimisation).
One string, many cut points
The single-string problems (word break, palindrome partitioning) use a different picture: a row of possible cut positions between letters. For catsand there are 8 positions, 0 to 7. Position 0 is before c, position 7 is after d. A segmentation is a set of jumps from 0 to 7 where each jump covers a valid piece.
flowchart LR
P0(("0")) -->|"cat"| P3(("3"))
P0 -->|"cats"| P4(("4"))
P3 -->|"sand"| P7(("7"))
P4 -->|"and"| P7
P1(("1"))
P2(("2"))
P5(("5"))
P6(("6"))
Each arrow is a dictionary word starting at one position and ending at another. "Can catsand be broken?" becomes "is there a path from 0 to 7?". dp[i] = "is position i reachable from 0?". Positions 1, 2, 5 and 6 have no arrows in: no word ends there in a valid split.
The shared recipe
| Problem | State | Transition (in words) | Base case | Answer |
|---|---|---|---|---|
| Word break | dp[i]: can s[:i] be split | some j < i with dp[j] and s[j:i] a word | dp[0] = true | dp[n] |
| Wildcard | dp[i][j]: s[:i] matches p[:j] | letter/?: diagonal; *: left or up | dp[0][0] = true, row 0 true while only stars | dp[m][n] |
| Regex | dp[i][j]: s[:i] matches p[:j] | letter/.: diagonal; x*: two left or (fits and up) | dp[0][0] = true, row 0 via x* vanishing | dp[m][n] |
| Distinct subsequences | dp[i][j]: ways to pick t[:j] from s[:i] | up, plus diagonal if letters equal | dp[i][0] = 1 | dp[m][n] |
| Interleaving | dp[i][j]: c[:i+j] from a[:i] and b[:j] | up if a[i-1] fits, or left if b[j-1] fits | dp[0][0] = true | dp[m][n] |
| Palindrome min cut | cut[j]: fewest cuts for s[:j+1] | over palindromes s[i..j]: cut[i-1] + 1 | 0 if s[:j+1] is a palindrome | cut[n-1] |
Read this table twice. The rest of the lesson is six careful walks through it.
How to read the indices
dp[i][j] talks about the prefixes s[:i] and p[:j], so the last letters of those prefixes are s[i-1] and p[j-1]. The table is one bigger than the strings in each direction because of the empty prefix. Almost every off-by-one bug in string DP is mixing up "length i" with "index i".
1. Word break
The problem
Given a string s and a list of words, decide whether s can be cut into pieces that are all in the list. Words may be reused. Example: s = "catsand", words cat, cats, and, sand. Yes: cat | sand or cats | and.
By hand
A teacher at a whiteboard would say: "Let's walk along the string and, at every position, write down whether we could have arrived there by a chain of whole words."
- Position 0 (before anything): yes, trivially. We have used no words.
- Position 1 (
c): isca word? No. Not reachable. - Position 2 (
ca):cais not a word, and position 1 was not reachable soaalone does not help. No. - Position 3 (
cat):catis a word and position 0 is reachable. Yes. - Position 4 (
cats):catsis a word from position 0. Yes. - Position 5 (
catsa): try every last word ending here:catsa,atsa,tsa,sa,a. The only starting points that are reachable are 0, 3, 4, andcatsa,sa,aare not words. No. - Position 6 (
catsan):catsan,san,anfrom 0, 3, 4. No. - Position 7 (
catsand): from 3, the last word would besand(a word). Yes. (From 4,andalso works.)
So dp = [T, F, F, T, T, F, F, T] and the answer is dp[7] = T.
Trace table
The table below was produced by running the Python code from this page with the inner loop scanning j = 0, 1, …, i-1 and stopping at the first success.
i | prefix s[:i] | reachable j tried | last piece s[j:i] that works | dp[i] |
|---|---|---|---|---|
| 0 | ε | (base) | — | T |
| 1 | c | 0 | none (c) | F |
| 2 | ca | 0 | none (ca) | F |
| 3 | cat | 0 | cat (from 0) | T |
| 4 | cats | 0 | cats (from 0) | T |
| 5 | catsa | 0, 3, 4 | none (catsa, sa, a) | F |
| 6 | catsan | 0, 3, 4 | none (catsan, san, an) | F |
| 7 | catsand | 0, 3 | sand (from 3) | T |
Each dp[i] reads every earlier dp[j]. To print one segmentation, remember the j that worked (a back pointer) and walk back from the end: 7 came from 3 (sand), 3 came from 0 (cat), giving cat sand.
The transition, written down
means "or over all", means "and", and is the piece from index up to but not including .
A cheap but large speed-up: if the longest word has length , the last piece can be at most long, so only needs checking. That turns substring checks into .
Deeper: what each step really costs
With a hash set, "is s[j:i] a word" costs to build and hash the slice, not . The honest bound for the plain double loop is in the worst case, and with the length bound. Two ways to remove the slice cost:
- A trie of the words. From each reachable position
j, walk the trie forward alongs[j], s[j+1], …; every word-end node you pass marksdp[j + len]reachable. Total work character steps, with no slicing at all. This is the standard solution for CSES "Word Combinations", where you count splits instead of checking one. - Rolling hashes of the words, compared against rolling hashes of
s. See String Hashing.
For many words and long s, Aho–Corasick finds every (start, end) occurrence of every word in one pass, in time linear in the text plus the number of matches.
Code: word break with one reconstructed split
def word_break(s: str, words: list[str]) -> list[str] | None:
"""Return one way to split s into words (reuse allowed), or None if impossible."""
vocab = set(words)
longest = max((len(w) for w in vocab), default=0)
n = len(s)
back = [-1] * (n + 1) # back[i] = start of the last word in a split of s[:i]; -1 = unreachable
back[0] = 0
for i in range(1, n + 1):
for j in range(max(0, i - longest), i):
if back[j] != -1 and s[j:i] in vocab:
back[i] = j
break
if back[n] == -1:
return None
pieces, i = [], n
while i > 0:
pieces.append(s[back[i]:i])
i = back[i]
return pieces[::-1]
if __name__ == "__main__":
assert word_break("catsand", ["cat", "cats", "and", "sand"]) == ["cat", "sand"]
assert word_break("leetcode", ["leet", "code"]) == ["leet", "code"]
assert word_break("applepenapple", ["apple", "pen"]) == ["apple", "pen", "apple"]
assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) is None
assert word_break("", ["a"]) == []
assert word_break("aaaaaaaab", ["a", "aa", "aaa"]) is None
print("word break ok")
import java.util.*;
public class WordBreak {
/** One way to split s into words (reuse allowed), or null if impossible. */
static List<String> wordBreak(String s, List<String> words) {
Set<String> vocab = new HashSet<>(words);
int longest = 0;
for (String w : vocab) longest = Math.max(longest, w.length());
int n = s.length();
int[] back = new int[n + 1]; // start of the last word, -1 = unreachable
Arrays.fill(back, -1);
back[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = Math.max(0, i - longest); j < i; j++) {
if (back[j] != -1 && vocab.contains(s.substring(j, i))) {
back[i] = j;
break;
}
}
}
if (back[n] == -1) return null;
LinkedList<String> pieces = new LinkedList<>();
for (int i = n; i > 0; i = back[i]) pieces.addFirst(s.substring(back[i], i));
return pieces;
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(wordBreak("catsand", List.of("cat", "cats", "and", "sand")).equals(List.of("cat", "sand")), "catsand");
check(wordBreak("leetcode", List.of("leet", "code")).equals(List.of("leet", "code")), "leetcode");
check(wordBreak("applepenapple", List.of("apple", "pen")).equals(List.of("apple", "pen", "apple")), "apple");
check(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")) == null, "catsandog");
check(wordBreak("", List.of("a")).isEmpty(), "empty");
check(wordBreak("aaaaaaaab", List.of("a", "aa", "aaa")) == null, "aab");
System.out.println("word break ok");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
// One way to split s into words (reuse allowed). Returns false if impossible.
bool wordBreak(const std::string& s, const std::vector<std::string>& words, std::vector<std::string>& pieces) {
std::unordered_set<std::string> vocab(words.begin(), words.end());
int longest = 0;
for (const auto& w : vocab) longest = std::max(longest, static_cast<int>(w.size()));
int n = static_cast<int>(s.size());
std::vector<int> back(n + 1, -1); // start of the last word, -1 = unreachable
back[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = std::max(0, i - longest); j < i; ++j) {
if (back[j] != -1 && vocab.count(s.substr(j, i - j))) {
back[i] = j;
break;
}
}
}
pieces.clear();
if (back[n] == -1) return false;
for (int i = n; i > 0; i = back[i]) pieces.push_back(s.substr(back[i], i - back[i]));
std::reverse(pieces.begin(), pieces.end());
return true;
}
int main() {
std::vector<std::string> out;
assert(wordBreak("catsand", {"cat", "cats", "and", "sand"}, out));
assert((out == std::vector<std::string>{"cat", "sand"}));
assert(wordBreak("leetcode", {"leet", "code"}, out));
assert((out == std::vector<std::string>{"leet", "code"}));
assert(wordBreak("applepenapple", {"apple", "pen"}, out));
assert((out == std::vector<std::string>{"apple", "pen", "apple"}));
assert(!wordBreak("catsandog", {"cats", "dog", "sand", "and", "cat"}, out));
assert(wordBreak("", {"a"}, out) && out.empty());
assert(!wordBreak("aaaaaaaab", {"a", "aa", "aaa"}, out));
std::cout << "word break ok\n";
}
/** One way to split s into words (reuse allowed), or null if impossible. */
function wordBreak(s: string, words: string[]): string[] | null {
const vocab = new Set(words);
let longest = 0;
for (const w of vocab) longest = Math.max(longest, w.length);
const n = s.length;
const back: number[] = new Array(n + 1).fill(-1); // start of the last word, -1 = unreachable
back[0] = 0;
for (let i = 1; i <= n; i++) {
for (let j = Math.max(0, i - longest); j < i; j++) {
if (back[j] !== -1 && vocab.has(s.slice(j, i))) {
back[i] = j;
break;
}
}
}
if (back[n] === -1) return null;
const pieces: string[] = [];
for (let i = n; i > 0; i = back[i]) pieces.push(s.slice(back[i], i));
return pieces.reverse();
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("failed: " + what);
}
const same = (a: string[] | null, b: string[]): boolean => a !== null && a.join("|") === b.join("|") && a.length === b.length;
check(same(wordBreak("catsand", ["cat", "cats", "and", "sand"]), ["cat", "sand"]), "catsand");
check(same(wordBreak("leetcode", ["leet", "code"]), ["leet", "code"]), "leetcode");
check(same(wordBreak("applepenapple", ["apple", "pen"]), ["apple", "pen", "apple"]), "apple");
check(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) === null, "catsandog");
check(same(wordBreak("", ["a"]), []), "empty");
check(wordBreak("aaaaaaaab", ["a", "aa", "aaa"]) === null, "aab");
console.log("word break ok");
The aaaaaaaab test is the classic trap for plain recursion: every prefix of as can be split in many ways, so a non-memoized search tries exponentially many splits before discovering that the b can never be covered. The table answers it in slice checks.
2. Wildcard matching
The problem
A pattern contains ordinary letters, ? (matches exactly one character, any character) and * (matches any sequence of characters, including none). The match must cover the whole text. Does s match p?
Example: s = "adceb", p = "*a*b". Yes: the first * takes nothing, a matches a, the second * takes dce, and b matches b.
The three cases for the last pattern character
To decide dp[i][j] (does s[:i] match p[:j]?), look at the last pattern character p[j-1]:
flowchart TD
Q{"What is p[j-1]?"}
Q -->|"a letter equal to s[i-1], or ?"| D["use dp[i-1][j-1]<br/>both last characters consumed"]
Q -->|"a letter different from s[i-1]"| F["false"]
Q -->|"*"| S{"star choice"}
S -->|"star matches nothing"| L["dp[i][j-1]<br/>drop the star"]
S -->|"star swallows s[i-1] and maybe more"| U["dp[i-1][j]<br/>keep the star, drop a text letter"]
The star case is the only interesting one. A star that matches the empty string can simply be deleted from the pattern: that is the cell to the left. A star that matches at least one character must have swallowed the last text letter s[i-1], and the same star is still there to swallow more: that is the cell above, same column because the star is not used up. This "stay in the same column" move is what lets one star absorb any number of letters without a loop.
Base cases: dp[0][0] = true (empty matches empty); dp[i][0] = false for i > 0 (a non-empty text never matches an empty pattern); dp[0][j] is true exactly while p[:j] is all stars.
The full table for adceb vs *a*b
Rows are text prefixes, columns pattern prefixes. Produced by the trace generator scripts/traces/wildcard_matching_dp.py.
s[:i] \ p[:j] | ε | * | a | * | b |
|---|---|---|---|---|---|
| ε | T | T | F | F | F |
a | F | T | T | T | F |
d | F | T | F | T | F |
c | F | T | F | T | F |
e | F | T | F | T | F |
b | F | T | F | T | T |
Dry run, cell by cell
Row 1 onwards, filled left to right. "Reads" names the cells the new cell looks at.
| Step | Cell | s[i-1], p[j-1] | Case | Reads | Value |
|---|---|---|---|---|---|
| 1 | dp[1][1] | a, * | star | left dp[1][0] = F, up dp[0][1] = T | T |
| 2 | dp[1][2] | a, a | equal letters | diagonal dp[0][1] = T | T |
| 3 | dp[1][3] | a, * | star | left dp[1][2] = T, up dp[0][3] = F | T |
| 4 | dp[1][4] | a, b | different | — | F |
| 5 | dp[2][1] | d, * | star | left F, up dp[1][1] = T | T |
| 6 | dp[2][2] | d, a | different | — | F |
| 7 | dp[2][3] | d, * | star | left dp[2][2] = F, up dp[1][3] = T | T |
| 8 | dp[2][4] | d, b | different | — | F |
| 9–16 | rows c, e | same shape as row d | T F T F | ||
| 17 | dp[5][1] | b, * | star | up dp[4][1] = T | T |
| 18 | dp[5][2] | b, a | different | — | F |
| 19 | dp[5][3] | b, * | star | left F, up dp[4][3] = T | T |
| 20 | dp[5][4] | b, b | equal letters | diagonal dp[4][3] = T | T |
Look at column 3 (the second star): once dp[1][3] became true, the "up" rule carried the truth straight down the column. That vertical run of T's is the star swallowing d, then c, then e, then b. The final diagonal step from dp[4][3] says: "let the star stop after e, and match b with b".
In the visualizer the cell being filled is amber, the cells it reads are cyan, and true cells are green.
Deeper: the greedy two-pointer that needs no table
For wildcard patterns (not regex) there is a well-known -extra-space algorithm, often credited in this form to Kirk Krauss (Dr. Dobb's, 2008) and used in many glob libraries. Walk i over the text and j over the pattern. On a letter or ? that fits, advance both. On a *, remember its position star = j and the text position mark = i, then advance only j (try "star matches nothing" first). On a mismatch, if a star was seen, backtrack: j = star + 1, mark += 1, i = mark (let the most recent star swallow one more letter). Otherwise fail. At the end, skip trailing stars.
Why only the most recent star? If the part of the pattern between two stars can be matched somewhere, matching it at the earliest place never hurts: the later star can absorb whatever the earlier choice left over. So earlier stars never need to be revisited. The worst case is still (for patterns like *aaaab against long runs of a), but typical inputs are near linear and memory is constant. The DP stays the right tool when you need counting, or when the pattern language grows beyond ? and *.
3. Regex matching with . and *
What changes
In this regex dialect, . matches any one character, and * means "zero or more copies of the character just before it". So a* matches ε, a, aa, …; .* matches anything; c*a*b matches b, ab, cab, ccaab, and also aab.
The big difference from wildcards: a * is never a token on its own. x* is one token, two characters wide. That is why the regex transition looks two columns back.
The cases
Look at p[j-1]:
- A letter or
.: it must matchs[i-1]. Thendp[i][j] = dp[i-1][j-1](diagonal). Otherwise false. *: the token isx* = p[j-2] p[j-1]. Two choices:- zero copies: the whole token disappears, so
dp[i][j-2](two columns left). - one more copy: allowed only if
xfits the last text letter (x == s[i-1]orx == '.'). Then the token swallowss[i-1]and stays available:dp[i-1][j](up, same column, exactly like the wildcard star).
- zero copies: the whole token disappears, so
where is true when or .
flowchart TD
T{"Is p[j-1] a star?"}
T -->|"no"| N{"fits(s[i-1], p[j-1])?"}
N -->|"yes"| DG["dp[i-1][j-1]"]
N -->|"no"| FF["false"]
T -->|"yes, token is x*"| Z["zero copies: dp[i][j-2]"]
T -->|"yes, token is x*"| O{"fits(s[i-1], x)?"}
O -->|"yes"| UP["one more copy: dp[i-1][j]"]
O -->|"no"| FF
Z --> OR(("or"))
UP --> OR
Row 0 needs care: the empty text matches p[:j] only if p[:j] is a chain of x* tokens, each vanishing. So dp[0][j] = (p[j-1] == '*') and dp[0][j-2].
The table for aab vs c*a*b
From scripts/traces/regex_matching_dp.py:
s[:i] \ p[:j] | ε | c | * | a | * | b |
|---|---|---|---|---|---|---|
| ε | T | F | T | F | T | F |
a | F | F | F | T | T | F |
a | F | F | F | F | T | F |
b | F | F | F | F | F | T |
Dry run
| Step | Cell | Token | Reads | Reasoning | Value |
|---|---|---|---|---|---|
| r0 | dp[0][2] | c* | dp[0][0] = T | c* vanishes | T |
| r0 | dp[0][4] | a* | dp[0][2] = T | c*a* vanishes | T |
| 1 | dp[1][1] | c | — | a ≠ c | F |
| 2 | dp[1][2] | c* | dp[1][0] = F | zero copies fails; a does not fit c | F |
| 3 | dp[1][3] | a | diagonal dp[0][2] = T | a = a, and c* matched ε | T |
| 4 | dp[1][4] | a* | dp[1][2] = F, up dp[0][4] = T | one copy of a | T |
| 5 | dp[1][5] | b | — | a ≠ b | F |
| 6–7 | dp[2][1..2] | c, c* | no c anywhere | F, F | |
| 8 | dp[2][3] | a | diagonal dp[1][2] = F | c* cannot match a | F |
| 9 | dp[2][4] | a* | dp[2][2] = F, up dp[1][4] = T | a second copy of a | T |
| 10 | dp[2][5] | b | — | a ≠ b | F |
| 11–14 | dp[3][1..4] | b fits neither c nor a | F | ||
| 15 | dp[3][5] | b | diagonal dp[2][4] = T | b = b | T |
Notice the vertical pair of T's in column 4: a* swallowed the first a, then the second. Then the final b closes the match diagonally. Step 8 is worth staring at: dp[2][3] asks "does aa match c*a?" and the answer is no, because the single literal a can take only one letter. It is the star column that absorbs repeats, never the literal column.
A second example where the answer is false
s = "mississippi", p = "mis*is*p*." is false (computed: the last row of the 12 × 11 table is all F). By hand: the pattern produces mi, some ss, i, some ss, some ps, then exactly one more character. The best it can do with the text is mi + ss + i + ss, leaving ippi, and ippi is not "some ps followed by one character" because it starts with i and is four letters long. The table discovers this mechanically, without that reasoning.
Deeper: how real regex engines do this
Our DP is a special case of simulating a nondeterministic finite automaton (NFA) over the text. Ken Thompson's 1968 construction turns any regular expression into an NFA with states; running it over a text of length by tracking the set of active states costs , the same as our table. A DP row is exactly that set of active states: dp[i][j] true means "after reading i letters, the automaton can be at pattern position j".
Backtracking engines (PCRE, Java's java.util.regex, Python's re) instead try one choice at a time and back up on failure. They support backreferences, which no finite automaton can, but pay for it with exponential worst cases: (a*)*b against aaaa…a is the classic "catastrophic backtracking" example. Russ Cox's article Regular Expression Matching Can Be Simple And Fast (2007) explains the gap, and Google's RE2 and Rust's regex crate are built on the automaton approach for exactly this reason. The full story is in Regex Engines.
Code: wildcard and regex matching
Both functions use the full table so that they mirror the walkthrough. The regex version runs its outer loop from i = 0, so row 0 (empty text) uses the same rule as every other row; the i > 0 guards make the "letter" and "one more copy" branches false on row 0. The pattern is assumed valid: a * never comes first.
def wildcard_match(s: str, p: str) -> bool:
"""'?' matches one character, '*' matches any sequence (including empty)."""
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and p[j - 1] == "*"
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
dp[i][j] = dp[i][j - 1] or dp[i - 1][j] # star takes nothing / one more char
elif p[j - 1] == "?" or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
def regex_match(s: str, p: str) -> bool:
"""'.' matches one character, 'x*' matches zero or more copies of x."""
m, n = len(s), len(p)
def fits(a: str, b: str) -> bool:
return b == "." or a == b
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
dp[i][j] = dp[i][j - 2] or (i > 0 and fits(s[i - 1], p[j - 2]) and dp[i - 1][j])
else:
dp[i][j] = i > 0 and fits(s[i - 1], p[j - 1]) and dp[i - 1][j - 1]
return dp[m][n]
if __name__ == "__main__":
assert wildcard_match("adceb", "*a*b")
assert not wildcard_match("acdcb", "a*c?b")
assert not wildcard_match("aa", "a")
assert wildcard_match("aa", "*")
assert not wildcard_match("cb", "?a")
assert wildcard_match("", "***")
assert not wildcard_match("", "?")
assert regex_match("aab", "c*a*b")
assert not regex_match("mississippi", "mis*is*p*.")
assert regex_match("ab", ".*")
assert not regex_match("aa", "a")
assert regex_match("aa", "a*")
assert regex_match("", "a*b*")
assert not regex_match("ab", ".*c")
print("matching ok")
public class PatternMatching {
/** '?' matches one character, '*' matches any sequence (including empty). */
static boolean wildcardMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char pc = p.charAt(j - 1);
if (pc == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if (pc == '?' || pc == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[m][n];
}
static boolean fits(char a, char b) {
return b == '.' || a == b;
}
/** '.' matches one character, 'x*' matches zero or more copies of x. */
static boolean regexMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2]
|| (i > 0 && fits(s.charAt(i - 1), p.charAt(j - 2)) && dp[i - 1][j]);
} else {
dp[i][j] = i > 0 && fits(s.charAt(i - 1), p.charAt(j - 1)) && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(wildcardMatch("adceb", "*a*b"), "w1");
check(!wildcardMatch("acdcb", "a*c?b"), "w2");
check(!wildcardMatch("aa", "a"), "w3");
check(wildcardMatch("aa", "*"), "w4");
check(!wildcardMatch("cb", "?a"), "w5");
check(wildcardMatch("", "***"), "w6");
check(!wildcardMatch("", "?"), "w7");
check(regexMatch("aab", "c*a*b"), "r1");
check(!regexMatch("mississippi", "mis*is*p*."), "r2");
check(regexMatch("ab", ".*"), "r3");
check(!regexMatch("aa", "a"), "r4");
check(regexMatch("aa", "a*"), "r5");
check(regexMatch("", "a*b*"), "r6");
check(!regexMatch("ab", ".*c"), "r7");
System.out.println("matching ok");
}
}
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
// '?' matches one character, '*' matches any sequence (including empty).
bool wildcardMatch(const std::string& s, const std::string& p) {
std::size_t m = s.size(), n = p.size();
std::vector<std::vector<char>> dp(m + 1, std::vector<char>(n + 1, 0));
dp[0][0] = 1;
for (std::size_t j = 1; j <= n; ++j) dp[0][j] = dp[0][j - 1] && p[j - 1] == '*';
for (std::size_t i = 1; i <= m; ++i) {
for (std::size_t j = 1; j <= n; ++j) {
if (p[j - 1] == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[m][n];
}
static bool fits(char a, char b) { return b == '.' || a == b; }
// '.' matches one character, 'x*' matches zero or more copies of x.
bool regexMatch(const std::string& s, const std::string& p) {
std::size_t m = s.size(), n = p.size();
std::vector<std::vector<char>> dp(m + 1, std::vector<char>(n + 1, 0));
dp[0][0] = 1;
for (std::size_t i = 0; i <= m; ++i) {
for (std::size_t j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2] || (i > 0 && fits(s[i - 1], p[j - 2]) && dp[i - 1][j]);
} else {
dp[i][j] = i > 0 && fits(s[i - 1], p[j - 1]) && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
int main() {
assert(wildcardMatch("adceb", "*a*b"));
assert(!wildcardMatch("acdcb", "a*c?b"));
assert(!wildcardMatch("aa", "a"));
assert(wildcardMatch("aa", "*"));
assert(!wildcardMatch("cb", "?a"));
assert(wildcardMatch("", "***"));
assert(!wildcardMatch("", "?"));
assert(regexMatch("aab", "c*a*b"));
assert(!regexMatch("mississippi", "mis*is*p*."));
assert(regexMatch("ab", ".*"));
assert(!regexMatch("aa", "a"));
assert(regexMatch("aa", "a*"));
assert(regexMatch("", "a*b*"));
assert(!regexMatch("ab", ".*c"));
std::cout << "matching ok\n";
}
/** '?' matches one character, '*' matches any sequence (including empty). */
function wildcardMatch(s: string, p: string): boolean {
const m = s.length, n = p.length;
const dp: boolean[][] = Array.from({ length: m + 1 }, () => new Array<boolean>(n + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] && p[j - 1] === "*";
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j - 1] === "*") dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
else if (p[j - 1] === "?" || p[j - 1] === s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[m][n];
}
const fits = (a: string, b: string): boolean => b === "." || a === b;
/** '.' matches one character, 'x*' matches zero or more copies of x. */
function regexMatch(s: string, p: string): boolean {
const m = s.length, n = p.length;
const dp: boolean[][] = Array.from({ length: m + 1 }, () => new Array<boolean>(n + 1).fill(false));
dp[0][0] = true;
for (let i = 0; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j - 1] === "*") {
dp[i][j] = dp[i][j - 2] || (i > 0 && fits(s[i - 1], p[j - 2]) && dp[i - 1][j]);
} else {
dp[i][j] = i > 0 && fits(s[i - 1], p[j - 1]) && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("failed: " + what);
}
check(wildcardMatch("adceb", "*a*b"), "w1");
check(!wildcardMatch("acdcb", "a*c?b"), "w2");
check(!wildcardMatch("aa", "a"), "w3");
check(wildcardMatch("aa", "*"), "w4");
check(!wildcardMatch("cb", "?a"), "w5");
check(wildcardMatch("", "***"), "w6");
check(!wildcardMatch("", "?"), "w7");
check(regexMatch("aab", "c*a*b"), "r1");
check(!regexMatch("mississippi", "mis*is*p*."), "r2");
check(regexMatch("ab", ".*"), "r3");
check(!regexMatch("aa", "a"), "r4");
check(regexMatch("aa", "a*"), "r5");
check(regexMatch("", "a*b*"), "r6");
check(!regexMatch("ab", ".*c"), "r7");
console.log("matching ok");
Wildcard `*` and regex `*` are different animals
In a glob, * is a free-standing token that matches any run. In a regex, * modifies the previous character. Transplanting the wildcard rule "left or up" into the regex problem gives wrong answers: under glob rules a* matches ab (the star takes b), but as a regex a* only matches runs of a, so ab does not match. Always ask "what does the star attach to?" before writing the transition.
4. Distinct subsequences
The problem
A subsequence of s is what you get by deleting some letters (maybe none) and keeping the rest in order. bag is a subsequence of babgbag in several ways. Count the number of different index choices that spell t inside s.
Example: s = "babgbag", t = "bag". Answer 5. Writing the chosen positions in capitals:
- BAbGbag, BAbgbaG, BabgbAG, baBgbAG, babgBAG
Thinking it through
Walk along s one letter at a time and keep, for every prefix t[:j] of the target, the number of ways to spell it using the letters seen so far. When a new letter s[i-1] arrives, every existing way stays valid (we may simply ignore this letter). In addition, if s[i-1] == t[j-1], each way of spelling t[:j-1] before this letter can be extended by using this letter as the final t[j-1].
dp[i][0] = 1 because there is exactly one way to spell the empty string: choose nothing. It is the seed every count grows from.
This is a counting DP: the two choices ("skip this letter" and "use this letter") lead to disjoint sets of index choices, so their counts add. Compare with the matching problems, where the choices combine with or.
Table and trace
Computed by the Python code below:
s[:i] \ t[:j] | ε | b | ba | bag |
|---|---|---|---|---|
| ε | 1 | 0 | 0 | 0 |
b | 1 | 1 | 0 | 0 |
a | 1 | 1 | 1 | 0 |
b | 1 | 2 | 1 | 0 |
g | 1 | 2 | 1 | 1 |
b | 1 | 3 | 1 | 1 |
a | 1 | 3 | 4 | 1 |
g | 1 | 3 | 4 | 5 |
| Row | New letter | Which j match | Update (reads up + diagonal) | Row after |
|---|---|---|---|---|
| 1 | b | j = 1 | dp[1][1] = 0 + 1 | 1 1 0 0 |
| 2 | a | j = 2 | dp[2][2] = 0 + 1 | 1 1 1 0 |
| 3 | b | j = 1 | dp[3][1] = 1 + 1 | 1 2 1 0 |
| 4 | g | j = 3 | dp[4][3] = 0 + 1 | 1 2 1 1 |
| 5 | b | j = 1 | dp[5][1] = 2 + 1 | 1 3 1 1 |
| 6 | a | j = 2 | dp[6][2] = 1 + 3 | 1 3 4 1 |
| 7 | g | j = 3 | dp[7][3] = 1 + 4 | 1 3 4 5 |
Row 6 is the interesting one: the second a can follow any of the three bs seen so far, so the count of ba jumps from 1 to 1 + 3 = 4.
One row is enough
Row i reads only row i-1. Keep one array dp[0..n] and, for each new letter, update j from right to left. Going right to left guarantees that when you read dp[j-1] it still holds the previous row's value. Going left to right would let one letter of s be used twice (as t[j-1] and then again as t[j]), which over-counts. The same reasoning as the 0/1 knapsack in Knapsack.
5. Interleaving strings
The problem
Can c be formed by merging a and b, where the letters of a appear in their original order, the letters of b appear in their original order, and every letter is used exactly once? Like shuffling two decks of cards together by riffling: each deck keeps its own order.
Example: a = "aab", b = "axy", c = "aaxaby". Yes:
c: a a x a b y
b a b a a b (which string each letter came from)
Reading the a-letters gives a a b and the b-letters give a x y. Swap c to abaaxy and the answer is no.
State and transition
If we have used i letters of a and j letters of b, we have built exactly c[:i+j]. So the pair (i, j) is the whole state. The last letter c[i+j-1] came either from a (then a[i-1] must equal it, and c[:i+j-1] was built from a[:i-1], b[:j]) or from b.
If len(a) + len(b) != len(c), the answer is no before any table work.
The table as a grid walk
Think of the table as a city grid. Start at the top-left corner. A step down uses the next letter of a, a step right uses the next letter of b. A step is allowed only if the letter it uses equals the next letter of c. c is an interleaving exactly when there is a monotone path from (0, 0) to (m, n). (This picture is a cousin of the path problems in Grid & Path DP.)
a[:i] \ b[:j] | ε | a | x | y |
|---|---|---|---|---|
| ε | T | T | F | F |
a | T | T | T | F |
a | T | F | T | F |
b | F | F | T | T |
The bold cells are one successful path: right (a from b), down (a from a), right (x), down (a), down (b), right (y). Cells that are T but not bold, such as dp[2][0] (aa from a's aa), are dead ends: true, but no path continues from them to the corner.
| Step | Cell (i, j) | Next letter of c | From up (a[i-1]) | From left (b[j-1]) | Value |
|---|---|---|---|---|---|
| 1 | (0, 1) | c[0] = a | — | dp[0][0] T, b[0] = a ✓ | T |
| 2 | (1, 0) | c[0] = a | dp[0][0] T, a[0] = a ✓ | — | T |
| 3 | (1, 1) | c[1] = a | dp[0][1] T, a[0] = a ✓ | T | |
| 4 | (1, 2) | c[2] = x | a[0] = a ✗ | dp[1][1] T, b[1] = x ✓ | T |
| 5 | (2, 1) | c[2] = x | a[1] = a ✗ | b[0] = a ✗ | F |
| 6 | (2, 2) | c[3] = a | dp[1][2] T, a[1] = a ✓ | T | |
| 7 | (3, 2) | c[4] = b | dp[2][2] T, a[2] = b ✓ | T | |
| 8 | (3, 3) | c[5] = y | a[2] = b ✗ | dp[3][2] T, b[2] = y ✓ | T |
(Only the cells on or next to the path are listed; the full table above has every cell.)
Deeper: why greedy fails, and the one-row version
A tempting shortcut: "take from a whenever its next letter matches, else from b". With a = "aab", b = "axy", c = "aaxaby" greedy takes a, a from a, then needs x; a's next letter is b, b's next letter is a. Stuck, and greedy says no, but the answer is yes. When both strings offer the same letter, the choice matters later. That is exactly the situation DP exists for.
Row i reads only row i-1 (up) and the current row (left), so one array of length n + 1 suffices: update dp[j] = (dp[j] and a[i-1] == c[i+j-1]) or (dp[j-1] and b[j-1] == c[i+j-1]) from left to right. Here left to right is correct, unlike distinct subsequences, because the "left" neighbour must already be the current row. Swap a and b if needed so the row is over the shorter string: memory.
Code: distinct subsequences and interleaving
def num_distinct(s: str, t: str) -> int:
"""Number of index choices that spell t as a subsequence of s."""
n = len(t)
dp = [1] + [0] * n # dp[j] = ways to spell t[:j] with the letters of s read so far
for ch in s:
for j in range(n, 0, -1): # right to left: dp[j-1] still holds the previous row
if t[j - 1] == ch:
dp[j] += dp[j - 1]
return dp[n]
def is_interleave(a: str, b: str, c: str) -> bool:
"""Can c be formed by merging a and b, keeping each one's letter order?"""
m, n = len(a), len(b)
if m + n != len(c):
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(m + 1):
for j in range(n + 1):
if i == 0 and j == 0:
continue
k = i + j - 1 # index in c of the letter placed last
from_a = i > 0 and dp[i - 1][j] and a[i - 1] == c[k]
from_b = j > 0 and dp[i][j - 1] and b[j - 1] == c[k]
dp[i][j] = from_a or from_b
return dp[m][n]
if __name__ == "__main__":
assert num_distinct("babgbag", "bag") == 5
assert num_distinct("rabbbit", "rabbit") == 3
assert num_distinct("abc", "") == 1
assert num_distinct("", "a") == 0
assert num_distinct("aaaa", "aa") == 6
assert is_interleave("aab", "axy", "aaxaby")
assert not is_interleave("aab", "axy", "abaaxy")
assert is_interleave("aabcc", "dbbca", "aadbbcbcac")
assert not is_interleave("aabcc", "dbbca", "aadbbbaccc")
assert is_interleave("", "", "")
assert not is_interleave("a", "", "aa")
print("counting ok")
public class SubsequenceAndInterleave {
/** Number of index choices that spell t as a subsequence of s. */
static long numDistinct(String s, String t) {
int n = t.length();
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
for (int j = n; j >= 1; j--) { // right to left: dp[j-1] is still the previous row
if (t.charAt(j - 1) == ch) dp[j] += dp[j - 1];
}
}
return dp[n];
}
/** Can c be formed by merging a and b, keeping each one's letter order? */
static boolean isInterleave(String a, String b, String c) {
int m = a.length(), n = b.length();
if (m + n != c.length()) return false;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 && j == 0) continue;
char last = c.charAt(i + j - 1);
boolean fromA = i > 0 && dp[i - 1][j] && a.charAt(i - 1) == last;
boolean fromB = j > 0 && dp[i][j - 1] && b.charAt(j - 1) == last;
dp[i][j] = fromA || fromB;
}
}
return dp[m][n];
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(numDistinct("babgbag", "bag") == 5, "bag");
check(numDistinct("rabbbit", "rabbit") == 3, "rabbit");
check(numDistinct("abc", "") == 1, "empty t");
check(numDistinct("", "a") == 0, "empty s");
check(numDistinct("aaaa", "aa") == 6, "aaaa");
check(isInterleave("aab", "axy", "aaxaby"), "i1");
check(!isInterleave("aab", "axy", "abaaxy"), "i2");
check(isInterleave("aabcc", "dbbca", "aadbbcbcac"), "i3");
check(!isInterleave("aabcc", "dbbca", "aadbbbaccc"), "i4");
check(isInterleave("", "", ""), "i5");
check(!isInterleave("a", "", "aa"), "i6");
System.out.println("counting ok");
}
}
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
// Number of index choices that spell t as a subsequence of s.
long long numDistinct(const std::string& s, const std::string& t) {
std::size_t n = t.size();
std::vector<long long> dp(n + 1, 0);
dp[0] = 1;
for (char ch : s) {
for (std::size_t j = n; j >= 1; --j) { // right to left: dp[j-1] is still the previous row
if (t[j - 1] == ch) dp[j] += dp[j - 1];
}
}
return dp[n];
}
// Can c be formed by merging a and b, keeping each one's letter order?
bool isInterleave(const std::string& a, const std::string& b, const std::string& c) {
std::size_t m = a.size(), n = b.size();
if (m + n != c.size()) return false;
std::vector<std::vector<char>> dp(m + 1, std::vector<char>(n + 1, 0));
dp[0][0] = 1;
for (std::size_t i = 0; i <= m; ++i) {
for (std::size_t j = 0; j <= n; ++j) {
if (i == 0 && j == 0) continue;
char last = c[i + j - 1];
bool fromA = i > 0 && dp[i - 1][j] && a[i - 1] == last;
bool fromB = j > 0 && dp[i][j - 1] && b[j - 1] == last;
dp[i][j] = fromA || fromB;
}
}
return dp[m][n];
}
int main() {
assert(numDistinct("babgbag", "bag") == 5);
assert(numDistinct("rabbbit", "rabbit") == 3);
assert(numDistinct("abc", "") == 1);
assert(numDistinct("", "a") == 0);
assert(numDistinct("aaaa", "aa") == 6);
assert(isInterleave("aab", "axy", "aaxaby"));
assert(!isInterleave("aab", "axy", "abaaxy"));
assert(isInterleave("aabcc", "dbbca", "aadbbcbcac"));
assert(!isInterleave("aabcc", "dbbca", "aadbbbaccc"));
assert(isInterleave("", "", ""));
assert(!isInterleave("a", "", "aa"));
std::cout << "counting ok\n";
}
/** Number of index choices that spell t as a subsequence of s. */
function numDistinct(s: string, t: string): number {
const n = t.length;
const dp: number[] = new Array(n + 1).fill(0);
dp[0] = 1;
for (const ch of s) {
for (let j = n; j >= 1; j--) {
// right to left: dp[j-1] is still the previous row
if (t[j - 1] === ch) dp[j] += dp[j - 1];
}
}
return dp[n];
}
/** Can c be formed by merging a and b, keeping each one's letter order? */
function isInterleave(a: string, b: string, c: string): boolean {
const m = a.length, n = b.length;
if (m + n !== c.length) return false;
const dp: boolean[][] = Array.from({ length: m + 1 }, () => new Array<boolean>(n + 1).fill(false));
dp[0][0] = true;
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i === 0 && j === 0) continue;
const last = c[i + j - 1];
const fromA = i > 0 && dp[i - 1][j] && a[i - 1] === last;
const fromB = j > 0 && dp[i][j - 1] && b[j - 1] === last;
dp[i][j] = fromA || fromB;
}
}
return dp[m][n];
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("failed: " + what);
}
check(numDistinct("babgbag", "bag") === 5, "bag");
check(numDistinct("rabbbit", "rabbit") === 3, "rabbit");
check(numDistinct("abc", "") === 1, "empty t");
check(numDistinct("", "a") === 0, "empty s");
check(numDistinct("aaaa", "aa") === 6, "aaaa");
check(isInterleave("aab", "axy", "aaxaby"), "i1");
check(!isInterleave("aab", "axy", "abaaxy"), "i2");
check(isInterleave("aabcc", "dbbca", "aadbbcbcac"), "i3");
check(!isInterleave("aabcc", "dbbca", "aadbbbaccc"), "i4");
check(isInterleave("", "", ""), "i5");
check(!isInterleave("a", "", "aa"), "i6");
console.log("counting ok");
Counts grow fast
num_distinct("a" * 40, "a" * 20) is , past 32-bit range. LeetCode 115 promises the answer fits in 32 bits, but intermediate cells can still be larger than the final answer in other inputs. Use 64-bit integers (as above), or take the answer modulo a prime when the problem asks. In TypeScript, number is exact only up to ; switch to bigint beyond that.
6. Palindrome partitioning
The problem
A palindrome reads the same forwards and backwards (aba, abba, a). Two questions about cutting a string s into pieces that are all palindromes:
- List every partition. For
aab:a | a | bandaa | b. - Find the fewest cuts. For
aab: 1 cut (aa | b). Forabaab: 1 cut (a | baab).
Step 1: a palindrome lookup table
Both questions ask "is s[i..j] a palindrome?" many times. Answer all of them once:
A piece is a palindrome when its two ends are equal and the inside is a palindrome (an inside of length 0 or 1 always is). pal[i][j] reads pal[i+1][j-1], the cell one row down and one column left, so fill i from the bottom up. This table is itself a small interval DP: the state is a substring, and shorter substrings are solved first.
For abaab (computed):
i \ j | 0 a | 1 b | 2 a | 3 a | 4 b |
|---|---|---|---|---|---|
0 a | T | F | T | F | F |
1 b | T | F | F | T | |
2 a | T | T | F | ||
3 a | T | F | |||
4 b | T |
The palindromes of length ≥ 2 are aba (0..2), aa (2..3) and baab (1..4).
Step 2a: list all partitions by backtracking
From position i, try every j ≥ i with pal[i][j], take the piece s[i..j], recurse from j + 1. When i reaches the end, record the current list of pieces.
flowchart TD
R["start at 0, string aab"] -->|"take a"| A1["at 1, pieces: a"]
R -->|"take aa"| A2["at 2, pieces: aa"]
R -.->|"aab is not a palindrome"| X1["skip"]
A1 -->|"take a"| B1["at 2, pieces: a a"]
A1 -.->|"ab is not a palindrome"| X2["skip"]
B1 -->|"take b"| C1["done: a | a | b"]
A2 -->|"take b"| C2["done: aa | b"]
The number of partitions can be exponential: a string of n identical letters has of them (every gap is cut or not). So listing is inherently exponential; the pal table only makes each check . This is a backtracking problem with a DP helper.
Step 2b: fewest cuts with a 1D DP
Let cut[j] be the fewest cuts needed for the prefix s[0..j]. If the whole prefix is a palindrome, cut[j] = 0. Otherwise the last piece is some palindrome s[i..j] with i ≥ 1, and the cuts before it are cut[i-1], plus one cut between i-1 and i:
The minimum is never over an empty set, since pal[j][j] (a single letter) is always true.
Trace for abaab (computed):
j | prefix | whole prefix palindrome? | candidates i with pal[i][j] → cut[i-1] + 1 | cut[j] |
|---|---|---|---|---|
| 0 | a | yes | — | 0 |
| 1 | ab | no | i=1 (b) → 0 + 1 | 1 |
| 2 | aba | yes | — | 0 |
| 3 | abaa | no | i=2 (aa) → 1 + 1 = 2, i=3 (a) → 0 + 1 = 1 | 1 |
| 4 | abaab | no | i=1 (baab) → 0 + 1 = 1, i=4 (b) → 1 + 1 = 2 | 1 |
Answer: 1 cut, a | baab. The pieces come from remembering which i won. The partition view of this problem (cutting a sequence into valid blocks, minimising the number or cost of blocks) is developed further in Partition DP.
Code: all partitions and minimum cuts
def palindrome_table(s: str) -> list[list[bool]]:
n = len(s)
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1): # pal[i][j] reads pal[i+1][j-1]: fill bottom-up
for j in range(i, n):
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
return pal
def all_partitions(s: str) -> list[list[str]]:
pal = palindrome_table(s)
out: list[list[str]] = []
pieces: list[str] = []
def go(i: int) -> None:
if i == len(s):
out.append(pieces.copy())
return
for j in range(i, len(s)):
if pal[i][j]:
pieces.append(s[i:j + 1])
go(j + 1)
pieces.pop()
go(0)
return out
def min_cut(s: str) -> int:
n = len(s)
if n == 0:
return 0
pal = palindrome_table(s)
cut = [0] * n
for j in range(n):
if not pal[0][j]:
cut[j] = min(cut[i - 1] + 1 for i in range(1, j + 1) if pal[i][j])
return cut[n - 1]
if __name__ == "__main__":
assert all_partitions("aab") == [["a", "a", "b"], ["aa", "b"]]
assert len(all_partitions("abaab")) == 4
assert all_partitions("a") == [["a"]]
assert len(all_partitions("aaaa")) == 8
assert min_cut("aab") == 1
assert min_cut("abaab") == 1
assert min_cut("a") == 0
assert min_cut("ab") == 1
assert min_cut("abcde") == 4
assert min_cut("racecar") == 0
print("palindromes ok")
import java.util.*;
public class PalindromePartitioning {
static boolean[][] palindromeTable(String s) {
int n = s.length();
boolean[][] pal = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) { // pal[i][j] reads pal[i+1][j-1]: fill bottom-up
for (int j = i; j < n; j++) {
pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
}
}
return pal;
}
static List<List<String>> allPartitions(String s) {
boolean[][] pal = palindromeTable(s);
List<List<String>> out = new ArrayList<>();
go(s, 0, pal, new ArrayDeque<>(), out);
return out;
}
private static void go(String s, int i, boolean[][] pal, Deque<String> pieces, List<List<String>> out) {
if (i == s.length()) {
out.add(new ArrayList<>(pieces));
return;
}
for (int j = i; j < s.length(); j++) {
if (pal[i][j]) {
pieces.addLast(s.substring(i, j + 1));
go(s, j + 1, pal, pieces, out);
pieces.removeLast();
}
}
}
static int minCut(String s) {
int n = s.length();
if (n == 0) return 0;
boolean[][] pal = palindromeTable(s);
int[] cut = new int[n];
for (int j = 0; j < n; j++) {
if (pal[0][j]) continue; // cut[j] stays 0
int best = Integer.MAX_VALUE;
for (int i = 1; i <= j; i++) {
if (pal[i][j]) best = Math.min(best, cut[i - 1] + 1);
}
cut[j] = best;
}
return cut[n - 1];
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(allPartitions("aab").equals(List.of(List.of("a", "a", "b"), List.of("aa", "b"))), "aab");
check(allPartitions("abaab").size() == 4, "abaab");
check(allPartitions("a").equals(List.of(List.of("a"))), "a");
check(allPartitions("aaaa").size() == 8, "aaaa");
check(minCut("aab") == 1, "c1");
check(minCut("abaab") == 1, "c2");
check(minCut("a") == 0, "c3");
check(minCut("ab") == 1, "c4");
check(minCut("abcde") == 4, "c5");
check(minCut("racecar") == 0, "c6");
System.out.println("palindromes ok");
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
std::vector<std::vector<char>> palindromeTable(const std::string& s) {
int n = static_cast<int>(s.size());
std::vector<std::vector<char>> pal(n, std::vector<char>(n, 0));
for (int i = n - 1; i >= 0; --i) { // pal[i][j] reads pal[i+1][j-1]: fill bottom-up
for (int j = i; j < n; ++j) {
pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
}
}
return pal;
}
static void go(const std::string& s, int i, const std::vector<std::vector<char>>& pal,
std::vector<std::string>& pieces, std::vector<std::vector<std::string>>& out) {
if (i == static_cast<int>(s.size())) {
out.push_back(pieces);
return;
}
for (int j = i; j < static_cast<int>(s.size()); ++j) {
if (pal[i][j]) {
pieces.push_back(s.substr(i, j - i + 1));
go(s, j + 1, pal, pieces, out);
pieces.pop_back();
}
}
}
std::vector<std::vector<std::string>> allPartitions(const std::string& s) {
std::vector<std::vector<char>> pal = palindromeTable(s);
std::vector<std::vector<std::string>> out;
std::vector<std::string> pieces;
go(s, 0, pal, pieces, out);
return out;
}
int minCut(const std::string& s) {
int n = static_cast<int>(s.size());
if (n == 0) return 0;
std::vector<std::vector<char>> pal = palindromeTable(s);
std::vector<int> cut(n, 0);
for (int j = 0; j < n; ++j) {
if (pal[0][j]) continue; // cut[j] stays 0
int best = INT_MAX;
for (int i = 1; i <= j; ++i) {
if (pal[i][j]) best = std::min(best, cut[i - 1] + 1);
}
cut[j] = best;
}
return cut[n - 1];
}
int main() {
std::vector<std::vector<std::string>> expect = {{"a", "a", "b"}, {"aa", "b"}};
assert(allPartitions("aab") == expect);
assert(allPartitions("abaab").size() == 4);
assert(allPartitions("aaaa").size() == 8);
assert(minCut("aab") == 1);
assert(minCut("abaab") == 1);
assert(minCut("a") == 0);
assert(minCut("ab") == 1);
assert(minCut("abcde") == 4);
assert(minCut("racecar") == 0);
std::cout << "palindromes ok\n";
}
function palindromeTable(s: string): boolean[][] {
const n = s.length;
const pal: boolean[][] = Array.from({ length: n }, () => new Array<boolean>(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
// pal[i][j] reads pal[i+1][j-1]: fill bottom-up
for (let j = i; j < n; j++) {
pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);
}
}
return pal;
}
function allPartitions(s: string): string[][] {
const pal = palindromeTable(s);
const out: string[][] = [];
const pieces: string[] = [];
const go = (i: number): void => {
if (i === s.length) {
out.push([...pieces]);
return;
}
for (let j = i; j < s.length; j++) {
if (pal[i][j]) {
pieces.push(s.slice(i, j + 1));
go(j + 1);
pieces.pop();
}
}
};
go(0);
return out;
}
function minCut(s: string): number {
const n = s.length;
if (n === 0) return 0;
const pal = palindromeTable(s);
const cut: number[] = new Array(n).fill(0);
for (let j = 0; j < n; j++) {
if (pal[0][j]) continue; // cut[j] stays 0
let best = Infinity;
for (let i = 1; i <= j; i++) {
if (pal[i][j]) best = Math.min(best, cut[i - 1] + 1);
}
cut[j] = best;
}
return cut[n - 1];
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("failed: " + what);
}
check(JSON.stringify(allPartitions("aab")) === JSON.stringify([["a", "a", "b"], ["aa", "b"]]), "aab");
check(allPartitions("abaab").length === 4, "abaab");
check(allPartitions("aaaa").length === 8, "aaaa");
check(minCut("aab") === 1, "c1");
check(minCut("abaab") === 1, "c2");
check(minCut("a") === 0, "c3");
check(minCut("ab") === 1, "c4");
check(minCut("abcde") === 4, "c5");
check(minCut("racecar") === 0, "c6");
console.log("palindromes ok");
The ladder: brute force → better → optimal
The same four rungs appear for every problem in this lesson. Take regex matching as the running example; the table at the end covers all six.
Rung 1: plain recursion
Write the definition directly: match(i, j) = does s[i:] match p[j:]? If p[j+1] is *, try "skip x*" (match(i, j+2)) and "use one copy" (match(i+1, j) when the letter fits). Otherwise compare one letter and call match(i+1, j+1).
It is correct, and it is exponential. Every x* is a fork, and the two forks of different stars reach the same (i, j) again and again. Against s = "aaaaaaaaaaaaaaaaaaab" and p = "a*a*a*a*a*a*c", the number of calls grows like the number of ways to distribute the as among six stars, roughly , and with more stars it gets worse. Backtracking regex engines live on this rung.
Rung 2: memoization (top-down DP)
Same recursion, plus a cache keyed by (i, j). There are only keys and each does work besides its recursive calls, so the total is . This is often the fastest rung to write in an interview: take the brute force, add @lru_cache. The recursion depth can reach , which is fine for strings of a few thousand characters in C++ and Java, and needs sys.setrecursionlimit (or a rewrite) in Python.
Rung 3: tabulation (bottom-up DP)
Fill the table in an order where every cell's inputs are ready: row by row, left to right, for the matching problems. time, space, no recursion, and the table is there to inspect, print and reconstruct from. All code on this page is on this rung.
Rung 4: rolling rows
Each row reads only itself and the row above, so keep two rows (or one, with the right update direction). time, space. You lose the ability to reconstruct the alignment unless you also keep back pointers or use a divide-and-conquer trick like Hirschberg's (see Sequence DP).
| Problem | Brute force | Memo / table | Space-optimised | Special shortcut |
|---|---|---|---|---|
| Word break | splits | checks, with length bound | already | Trie walk: character steps |
| Wildcard | exponential in the number of stars | Greedy star backtracking, space | ||
Regex . * | exponential | Thompson NFA simulation, | ||
| Distinct subsequences | subsets | , right to left | — | |
| Interleaving | choices | — | ||
| Palindrome min cut | cut sets | with the pal table | by expanding around centres | Palindromic tree / eertree methods, |
| All palindrome partitions | output-sensitive with pal | — | Output can be , no shortcut |
Why each rung is better, in one line each: memoization removes repeated subproblems; tabulation removes recursion overhead and stack limits; rolling rows removes memory that is never read again.
Correctness
All six DPs are proved the same way: induction on the size of the subproblem (the total prefix length , or the cut position). The base cases are true by definition. For the step, show two things about the transition: every way to get a "yes" (or every object being counted) is covered by one of the cases, and nothing the cases accept is wrong.
Word break
Claim: dp[i] is true exactly when s[:i] can be split into words. If a split exists and i > 0, look at its last word s[j:i]; the rest s[:j] is a split of a shorter prefix, so dp[j] is true by induction and the transition finds this j. Conversely, if the transition finds j with dp[j] and s[j:i] a word, append that word to the split of s[:j]. Both directions hold, so dp[n] is the answer.
Wildcard and regex
Claim: dp[i][j] is true exactly when s[:i] matches p[:j]. Look at how a match of s[:i] by p[:j] ends.
- If the last pattern token is a letter or
?/., it consumed exactly the last text letter, so the rest must be a match ofs[:i-1]byp[:j-1]: the diagonal. - If it is a wildcard
*, it consumed some number of trailing letters. : the rest is a match ofs[:i]byp[:j-1](left). : then the same star with letters is a match ofs[:i-1]byp[:j](up). Every is covered by one of these two, and each of them extends back to a real match. - If it is a regex
x*with copies: givesdp[i][j-2], and requires the last letter to fitx, after whichx*with copies matchess[:i-1]:dp[i-1][j].
The "up, same column" move is the heart of the proof: a star with letters is reduced to the same star with letters, a strictly smaller subproblem, so the induction is well founded.
Distinct subsequences
Claim: dp[i][j] counts index sequences with . Split those sequences by whether (the last letter of s[:i] is used). Those that do not use it are exactly the sequences counted by dp[i-1][j]. Those that do require , and removing leaves a sequence counted by dp[i-1][j-1]; adding it back is a one-to-one correspondence. The two groups are disjoint and together cover everything, so the counts add.
Interleaving
Claim: dp[i][j] is true exactly when c[:i+j] is an interleaving of a[:i] and b[:j]. In any such interleaving, the last letter c[i+j-1] is either a[i-1] or b[j-1], and deleting it leaves an interleaving of the shorter prefixes. Conversely, appending a matching letter to a valid shorter interleaving gives a valid one.
Palindrome minimum cuts
Claim: cut[j] is the minimum number of cuts for s[0..j]. In an optimal partition, the last piece is a palindrome s[i..j]. If there are no cuts. Otherwise, the pieces before it are a partition of s[0..i-1] with one fewer cut, and by optimality (any better partition of that prefix would improve the whole) it uses exactly cut[i-1] cuts. This is the optimal substructure argument from DP Foundations: the best whole contains a best prefix. The pal table is correct by induction on length: a string of length ≥ 2 is a palindrome iff its ends match and its middle is one.
Complexity
| Problem | Time | Space | Why |
|---|---|---|---|
| Word break (hash set) | end positions, start positions each, an slice to hash | ||
| Word break (trie) | one trie walk of at most steps from each reachable start | ||
| Wildcard, regex | , or rolling | cells, each | |
| Distinct subsequences | one pass of s, inner loop over t | ||
| Interleaving | , or | one cell per pair of prefixes | |
pal table | one cell per substring | ||
| Palindrome min cut | , or with centre expansion | ends × up to starts | |
| All partitions | worst case | plus output | output can be partitions of length up to |
The cost of a cell is "how many neighbours it reads". Two-string matching problems read at most three neighbours, so they are per cell. Word break and min cut read a whole range of earlier positions, so they are per cell, which is where the extra factor comes from. When a cell reads a range of earlier cells, look for a way to shrink the range (the word-length bound) or skip the range (the centre-expansion trick); DP Optimizations is the systematic version of that idea.
Real-world uses
- Shell globs and ignore files.
bash,fnmatch(3),.gitignore,.dockerignoreand build tools all match*and?patterns. Most use the greedy star-backtracking loop (the "Deeper" box in section 2) because it uses no memory; the DP is the reference you test it against. - Regex engines. RE2, Rust's
regexcrate and Go'sregexppackage simulate automata, which is the same set-of-states idea as a DP row, to guarantee time linear in the input for a fixed pattern. Backtracking engines (PCRE, Pythonre, Java) can blow up exponentially; this has caused real outages, for example the Cloudflare incident of 2 July 2019, where a regex with nested.*exhausted CPU across its network (Cloudflare blog, "Details of the Cloudflare outage on July 2, 2019"). - Word segmentation. Search engines split concatenated queries, domain names and hashtags (
#throwbackthursday). Languages written without spaces (Chinese, Japanese, Thai) need segmentation before indexing. Production segmenters replace the booleandp[i]with "best score of a segmentation ofs[:i]", where scores come from word frequencies: the same DP, withmaxinstead ofor. - Spell checking and autocorrect use edit distance, the sibling table from Sequence DP, often against a trie so the table rows are shared between words with a common prefix.
- Bioinformatics. Counting how often a short motif occurs as a gapped subsequence, aligning reads with gaps, and scoring interleavings of two sequences are all two-string tables with different scoring rules.
- Text editors. Breaking a paragraph into lines with the least ugliness (TeX's line-breaking algorithm by Knuth and Plass, 1981) is a cut-position DP, the same shape as word break with costs. See Partition DP.
Pitfalls & edge cases
- Empty strings. Every problem must handle
s = ""andp = "". The empty text matches***anda*b*, but not?ora. The empty target has exactly one occurrence as a subsequence. An empty string has zero palindrome cuts. Test these first. - Row 0 and column 0. Most wrong submissions get the interior transition right and the first row wrong. Wildcard: row 0 is true only while the pattern is all stars. Regex: row 0 is true only along a chain of
x*tokens, read two columns back. - Regex
*after...*means "any number of any characters". The "fits" check for one more copy must treat.as fitting every letter. - Indexing
p[j-2]. Only valid whenj ≥ 2. Valid regex patterns never start with*; if your input might, guard it. - Mixing up
ias a length and as an index.dp[i]is abouts[:i], whose last letter iss[i-1]. - Update direction in one-row tables. Distinct subsequences must update right to left; interleaving must update left to right. Ask "is the neighbour I read from the old row or the new row?"
- Overflow. Counts in distinct subsequences and in "number of ways to break" grow exponentially. Use 64-bit integers, or a modulus.
- Word break with huge dictionaries. Slicing
s[j:i]for every pair is slices. Bound by the longest word or use a trie. - Listing all results. Word Break II and palindrome partitioning can have exponentially many answers. A test like
"aaaa…a"with wordsa, aa, aaaexplodes; first check reachability (dp[n]) so unreachable inputs return quickly, and memoize on the start position. - Recursion depth. A memoized recursion on 10,000-character strings exceeds Python's default limit of 1000. Use the table.
Variations
- Count the number of ways (word break with counts, CSES Word Combinations): replace
orwith+and take a modulus. - Best-scoring segmentation: replace
orwithmaxand add a score per word; this is the unigram word segmenter used in many NLP toolkits. - Wildcard with
+(one or more):+is?followed by*. - Regex with
+and?quantifiers:x+isx x*;x?is "zero or one copy", sodp[i][j] = dp[i][j-2] or (fits and dp[i-1][j-2]), diagonal-two instead of up. - Regex with character classes
[a-c]: only thefitsfunction changes. - Edit distance to a pattern (approximate matching): add insert, delete and substitute moves with costs, and take
min. Theagreptool and the bitap algorithm are built on this. - Distinct subsequences II: count distinct strings that are subsequences, not index choices; subtract the count recorded at the previous occurrence of the same letter (practice problem 11).
- Longest palindromic subsequence and palindromic substrings: siblings of the
paltable, covered in Sequence DP and, for linear-time palindromes, Manacher. - Palindrome partitioning into exactly
kparts with fewest letter changes (practice problem 13): an interval cost table plus a partition DP over(position, parts). - Interleaving of three strings, or "is
ca shuffle ofaandbwith at mostkswitches": add a dimension for the extra quantity.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Is Subsequence (LeetCode 392) — Decide whether one string can be obtained from another by deleting letters. Teaches the two-finger picture before any table.
Hint
Two pointers: advance the pointer in t always, advance the pointer in s only on a match. The follow-up (many queries s against one fixed t) wants, for each position and letter, the next occurrence of that letter: a small DP from right to left.
2. Word Break (LeetCode 139) — Can a string be split into dictionary words. Teaches the cut-position table.
Hint
dp[0] = true; dp[i] is true if some reachable j has s[j:i] in the set. Bound j by the longest word. The code in section 1 is a full solution.
3. Palindrome Partitioning (LeetCode 131) — List every way to cut a string into palindromes. Teaches backtracking with a precomputed DP table.
Hint
Build pal[i][j] first, then recurse on the start position trying every palindromic piece. Section 6 has the code.
4. Interleaving String (LeetCode 97) — Can a third string be produced by merging two others in order. Teaches a two-string table where the "text" is the third string, indexed by i + j.
Hint
Check lengths first. dp[i][j] reads up (if a[i-1] == c[i+j-1]) and left (if b[j-1] == c[i+j-1]). The follow-up asks for extra memory: one row, updated left to right.
5. Distinct Subsequences (LeetCode 115) — Count the ways one string occurs as a subsequence of another. Teaches counting DP and the "skip or use" split.
Hint
dp[j] += dp[j-1] when the letters match, scanning j from right to left. Seed dp[0] = 1.
6. Word Break II (LeetCode 140) — Return every sentence that splits the string into dictionary words. Teaches memoized enumeration and output-sensitive cost.
Hint
Memoize "all sentences for the suffix starting at i". Each call tries every word that starts at i and prefixes it to each sentence of the remaining suffix.
Solution
from functools import lru_cache
def word_break_all(s: str, words: list[str]) -> list[str]:
vocab = set(words)
@lru_cache(maxsize=None)
def go(i: int) -> tuple[str, ...]:
if i == len(s):
return ("",)
out = []
for j in range(i + 1, len(s) + 1):
w = s[i:j]
if w in vocab:
for rest in go(j):
out.append(w if not rest else w + " " + rest)
return tuple(out)
return list(go(0))
assert sorted(word_break_all("catsanddog", ["cat", "cats", "and", "sand", "dog"])) == ["cat sand dog", "cats and dog"]
assert sorted(word_break_all("pineapplepenapple", ["apple", "pen", "applepen", "pine", "pineapple"])) == [
"pine apple pen apple", "pine applepen apple", "pineapple pen apple"]
assert word_break_all("catsandog", ["cats", "dog", "sand", "and", "cat"]) == []
Each suffix is solved once; the remaining cost is building the output strings, which is unavoidable. Returning a tuple keeps the cached value immutable.
7. Wildcard Matching (LeetCode 44) — Full-string match with ? and *. Teaches the left-or-up star rule, then the greedy alternative.
Hint
The table in section 2 passes. For memory, remember only the most recent star and the text position it started absorbing from.
Solution
The greedy version, checked against the DP from section 2 on random inputs:
import random
def wildcard_greedy(s: str, p: str) -> bool:
i = j = 0
star, mark = -1, 0 # last star in p, and where in s it started absorbing
while i < len(s):
if j < len(p) and (p[j] == "?" or p[j] == s[i]):
i += 1
j += 1
elif j < len(p) and p[j] == "*":
star, mark = j, i # first let the star match nothing
j += 1
elif star != -1:
mark += 1 # let the last star swallow one more letter
i, j = mark, star + 1
else:
return False
while j < len(p) and p[j] == "*":
j += 1
return j == len(p)
def wildcard_dp(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and p[j - 1] == "*"
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p[j - 1] in ("?", s[i - 1]):
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
rng = random.Random(7)
for _ in range(20000):
s = "".join(rng.choice("ab") for _ in range(rng.randint(0, 7)))
p = "".join(rng.choice("ab?*") for _ in range(rng.randint(0, 6)))
assert wildcard_greedy(s, p) == wildcard_dp(s, p), (s, p)
assert wildcard_greedy("adceb", "*a*b") and not wildcard_greedy("acdcb", "a*c?b")
worst case, extra memory.
8. Regular Expression Matching (LeetCode 10) — Full-string match with . and x*. Teaches tokens that span two characters.
Hint
Treat x* as one token: zero copies reads two columns left; one more copy (if x fits) reads up. Row 0 needs the same rule. Section 3 has the code.
9. Palindrome Partitioning II (LeetCode 132) — Fewest cuts so every piece is a palindrome. Teaches the 1D cut DP and how to drop the table.
Hint
cut[j] = min(cut[i-1] + 1) over palindromes s[i..j]. To save memory, expand around every centre instead: each palindrome s[lo..hi] found by expansion offers cut[hi+1] = cut[lo] + 1.
Solution
def min_cut_linear_space(s: str) -> int:
n = len(s)
cut = list(range(-1, n)) # cut[k] = fewest cuts for s[:k]; cut[0] = -1 so a whole palindrome gives 0
for centre in range(n):
for lo, hi in ((centre, centre), (centre, centre + 1)): # odd and even lengths
while lo >= 0 and hi < n and s[lo] == s[hi]:
cut[hi + 1] = min(cut[hi + 1], cut[lo] + 1)
lo -= 1
hi += 1
return cut[n]
for word, want in [("aab", 1), ("abaab", 1), ("a", 0), ("ab", 1), ("abcde", 4), ("racecar", 0), ("", -1)]:
assert min_cut_linear_space(word) == want, word
Every palindrome is discovered exactly once, from its centre, so the time is and the extra memory is . When s[lo..hi] is found, cut[lo] is already final because it depends only on palindromes ending before lo, and those all have centres earlier than the current one. Note that the empty string returns -1 here; guard it if your caller expects 0.
10. Word Combinations (CSES 1731) — Count the ways to build a long string from a dictionary, modulo . Teaches the trie-walk version of word break.
Hint
ways[i] = number of ways to build s[:i]. Insert the words into a trie. From each i with ways[i] > 0, walk the trie along s[i], s[i+1], …; at every word end at depth d, add ways[i] to ways[i + d]. This avoids slicing and runs in .
11. Distinct Subsequences II (LeetCode 940) — Count the different non-empty strings that occur as subsequences, modulo . Teaches de-duplicating a doubling count.
Hint
Appending letter c to every subsequence seen so far doubles the count, but the strings created the last time c appeared are created again. Subtract the count that existed just before that last c.
Solution
def distinct_subseq_ii(s: str) -> int:
MOD = 10**9 + 7
total = 1 # number of distinct subsequences so far, including the empty one
before_last: dict[str, int] = {} # total just before the previous occurrence of each letter
for ch in s:
new_total = (2 * total - before_last.get(ch, 0)) % MOD
before_last[ch] = total
total = new_total
return (total - 1) % MOD # drop the empty subsequence
assert distinct_subseq_ii("abc") == 7
assert distinct_subseq_ii("aba") == 6
assert distinct_subseq_ii("aaa") == 3
time, memory for the alphabet.
12. Concatenated Words (LeetCode 472) — Find every word in a list that is made of at least two shorter words from the same list. Teaches running word break many times efficiently.
Hint
Sort by length. For each word, run word break against the set of shorter words already seen (so a word cannot use itself), then add it to the set. The empty string must not count as a word.
13. Palindrome Partitioning III (LeetCode 1278) — Change as few letters as possible so the string can be cut into exactly k palindromes. Teaches combining an interval cost table with a partition DP.
Hint
cost[i][j] = letter changes to make s[i..j] a palindrome, from cost[i+1][j-1] plus one if the ends differ. Then best[p][j] = fewest changes to cut s[:j] into p palindromes, minimising over the start of the last piece. This is the (position, parts) shape of Partition DP.
Common mistakes & interview follow-ups
"Walk me through dp[i][j]." Say the meaning in words first ("does the first i letters of s match the first j letters of p"), then the base cases, then the cases on the last pattern character, then the fill order, then where the answer is. Interviewers mostly grade the meaning sentence: if it is precise, the code follows.
"Why does the star look up and not diagonally?" Because after the star swallows s[i-1] it is still available to swallow more. Moving diagonally would use it up after one letter, which is the semantics of ?, not *.
"Can you do it in less memory?" Yes for every two-string table here: two rows, or one row with the right update direction. Explain which direction and why. For wildcard specifically, the greedy algorithm uses .
"What if the pattern also has +, ? quantifiers or character classes?" Only the fits function and the quantifier cases change; derive each from "how many copies, and what does the smaller problem look like".
"Why not just use the language's regex library?" You can in production, after checking the engine type: backtracking engines can take exponential time on hostile patterns or inputs (ReDoS, regular expression denial of service). Automaton-based engines guarantee linear time for a fixed pattern.
"Return all solutions." Explain that the count can be exponential, so the cost is output-sensitive. Precompute reachability so dead branches are pruned, and memoize on the start position.
"What is the complexity of word break, really?" pairs times the cost of hashing a slice. Mention the longest-word bound and the trie, and you have answered the follow-up before it is asked.
Mistakes interviewers watch for: wrong row 0 for regex; using p[j-2] when j < 2; updating a one-row table in the wrong direction; forgetting the length check for interleaving; int overflow when counting; Python recursion limits on long inputs; claiming for word break while slicing inside the loop.
Quick quiz
1. In the wildcard table for adceb vs *a*b, why is the whole column under the second * true from row 1 down?
Answer
dp[1][3] is true (a matches *a*, with the second star empty). From there, every cell below reads "up" and inherits true: the second star swallows d, then c, then e, then b. A star column, once true, stays true going down.
2. For regex, why is dp[2][3] (aa against c*a) false even though dp[1][3] is true?
Answer
p[2] is a plain a, which consumes exactly one letter, so dp[2][3] reads only the diagonal dp[1][2] (a against c*), which is false. Only star columns can absorb repeated letters.
3. In distinct subsequences, what goes wrong if the one-row update runs left to right on s = "aa", t = "aa"?
Answer
Processing the first a: dp[1] += dp[0] makes dp[1] = 1, then dp[2] += dp[1] makes dp[2] = 1. That counted the same letter of s as both t[0] and t[1]. After the second a the result is 3 instead of the correct 1. Right to left reads the old dp[j-1] and gives 1.
4. What does dp[0][j] mean in the interleaving table, and when is it true?
Answer
It asks whether c[:j] can be built from no letters of a and the first j letters of b, i.e. whether c[:j] == b[:j]. It is true for a prefix of columns and then false forever.
5. For abaab, the min-cut DP gives cut = [0, 1, 0, 1, 1]. Which palindrome gives the final answer, and why is aba | a | b not optimal?
Answer
baab = s[1..4], giving cut[0] + 1 = 1 (a | baab). aba | a | b uses 2 cuts. The DP considered it, as i = 4 (b) with cut[3] + 1 = 2, and rejected it.
6. Word break on s of length with words of length at most 20: about how many substring checks does the bounded loop do?
Answer
At most checks (each hashing up to 20 characters), versus about pairs without the bound.
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (4th ed.), chapter 14 "Dynamic Programming", for the optimal-substructure argument and the LCS table these problems extend.
- Ken Thompson, "Programming Techniques: Regular expression search algorithm", Communications of the ACM 11(6), 1968: the NFA simulation behind automaton-based regex engines.
- Russ Cox, "Regular Expression Matching Can Be Simple And Fast" (2007), swtch.com/~rsc/regexp/regexp1.html: why backtracking engines blow up and automata do not.
- Kirk J. Krauss, "Matching Wildcards: An Algorithm", Dr. Dobb's Journal, 2008: the greedy star-backtracking matcher.
- Cloudflare, "Details of the Cloudflare outage on July 2, 2019" (blog.cloudflare.com): a production incident caused by regex backtracking.
- Donald E. Knuth and Michael F. Plass, "Breaking Paragraphs into Lines", Software: Practice and Experience 11(11), 1981: cut-position DP in TeX.
- CSES Problem Set, "String Algorithms" section (Word Combinations) and LeetCode problems 10, 44, 97, 115, 131, 132, 139, 140 for the statements referenced above.