These are the notes for DSA episode 73. A chat app wants one rule that catches hey, heyy and heyyyyyy: hey*, where a star means "any number of the letter before it, even zero", and a dot means "any one letter". Does a pattern match the whole message? We try a greedy star first (it eats too much: a wrong answer on screen), then both choices at every star recursively (correct, then Time Limit Exceeded on 30 a's), draw the key insight as a table, dp[i][j]: a star is zero copies (dp[i][j-2]) or one more copy (dp[i-1][j]), and type it live. Then a 2,000 × 2,000 table in milliseconds and three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| The chat filter | In code |
|---|---|
The message heyyyy |
the string s |
The rule hey* |
the pattern p |
| "any number of y's, even none" | y* |
"any one letter" (c.t: cat, cot, cut) |
. |
| "anything at all" | .* |
| The rule must explain the whole message | a full match, start to end |
Every word, from zero
- Regular expression (regex): a pattern describing a set of strings; every programming language has a regex library.
.(dot): matches exactly one character, any character.x*(star): matches zero or more copies ofx;xmay itself be.. The star always belongs to the character just before it.- Full match: the pattern must consume the entire string, not just a part of it.
- Greedy: a star that takes as many letters as it can and never gives any back.
- State:
(i, j): the firstiletters ofsand the firstjcharacters ofp. - Prefix: the first
icharacters; the empty prefix isi = 0. - Recurrence: the rule for
dp[i][j]from smaller cells (letter/dot: the diagonal; star: two options). - Base case:
dp[0][0] = true; row 0 (empty string) can still matcha*b*. - Memoization: the top-down alternative: cache
match(i, j)in aBoolean[][].
Problem statement
Regular Expression Matching (LeetCode 10). Implement matching with . and * that covers the entire input. 1 ≤ s.length ≤ 20, 1 ≤ p.length ≤ 20 on LeetCode; p is valid (every * follows a character).
| s | p | Answer | Why |
|---|---|---|---|
aa |
a |
false |
one a can't cover two |
aa |
a* |
true |
two copies |
ab |
.* |
true |
anything |
aab |
c*a*b |
true |
zero c's, two a's, one b |
mississippi |
mis*is*p*. |
false |
|
aaa |
a*a |
true |
a* takes two, a takes one |
ab |
.*b |
true |
.* takes a |
"" |
a* |
true |
zero copies |
"" |
"" |
true |
|
a |
"" |
false |
|
ab |
.*c |
false |
no c |
Obvious idea 1: a greedy star
import java.util.*;
public class Main {
static boolean isMatch(String s, String p) {
int i = 0, j = 0;
while (j < p.length()) {
char c = p.charAt(j);
boolean star = j + 1 < p.length() && p.charAt(j + 1) == '*';
if (star) {
while (i < s.length() && (c == '.' || s.charAt(i) == c)) i++;
j += 2;
} else {
if (i == s.length() || (c != '.' && s.charAt(i) != c)) return false;
i++;
j++;
}
}
return i == s.length();
}
public static void main(String[] args) {
System.out.println(isMatch("aa", "a"));
System.out.println(isMatch("aa", "a*"));
System.out.println(isMatch("ab", ".*"));
System.out.println(isMatch("aab", "c*a*b"));
System.out.println(isMatch("mississippi", "mis*is*p*."));
System.out.println(isMatch("aaa", "a*a"));
System.out.println(isMatch("ab", ".*b"));
}
}
false
true
true
true
false
false
false
The last two are wrong: a* ate all three a's and left nothing for the final a; .* ate the b. A star can't know how much to take until it sees the rest of the pattern.
Obvious idea 2: both choices at every star
match(i, j): does s from i match p from j? At a star: zero copies (j + 2) or, if the letter matches, eat one letter and stay (i + 1, same j).
import java.util.*;
public class Main {
static boolean isMatch(String s, String p) {
return match(s, 0, p, 0);
}
static boolean match(String s, int i, String p, int j) {
if (j == p.length()) return i == s.length();
boolean first = i < s.length() && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i));
if (j + 1 < p.length() && p.charAt(j + 1) == '*')
return match(s, i, p, j + 2) || (first && match(s, i + 1, p, j));
return first && match(s, i + 1, p, j + 1);
}
public static void main(String[] args) {
System.out.println(isMatch("aa", "a"));
System.out.println(isMatch("aa", "a*"));
System.out.println(isMatch("ab", ".*"));
System.out.println(isMatch("aab", "c*a*b"));
System.out.println(isMatch("mississippi", "mis*is*p*."));
System.out.println(isMatch("aaa", "a*a"));
System.out.println(isMatch("ab", ".*b"));
System.out.println(isMatch("", "a*"));
System.out.println(isMatch("", ""));
System.out.println(isMatch("a", ""));
System.out.println(isMatch("ab", ".*c"));
}
}
false
true
true
true
false
true
true
true
true
false
false
All correct. Now 30 a's against a* fifteen times and a c. There's no c, so the answer is false, but first every way to share 30 a's among 15 stars is tried (about 10^11):
import java.util.*;
public class Main {
static boolean isMatch(String s, String p) {
return match(s, 0, p, 0);
}
static boolean match(String s, int i, String p, int j) {
if (j == p.length()) return i == s.length();
boolean first = i < s.length() && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i));
if (j + 1 < p.length() && p.charAt(j + 1) == '*')
return match(s, i, p, j + 2) || (first && match(s, i + 1, p, j));
return first && match(s, i + 1, p, j + 1);
}
public static void main(String[] args) {
String s = "a".repeat(30);
String p = "a*".repeat(15) + "c";
long t0 = System.nanoTime();
boolean ok = isMatch(s, p);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("30 letters: " + ok + ", " + ms + " ms");
}
}
Time Limit Exceeded (stopped after 25 s)
Why is it slow?
- A call depends only on
(i, j). - "star 1 takes 2 a's, star 2 takes 0" and "each takes 1" both reach
(2, 4), and everything after is recomputed. - There are only
31 × 32pairs here.
The key insight: zero copies OR one more copy
| Case | Rule |
|---|---|
| State | dp[i][j] = do the first i letters of s match the first j characters of p? |
p[j-1] is a letter or . |
same(s[i-1], p[j-1]) && dp[i-1][j-1] |
p[j-1] is * after x |
dp[i][j-2] (zero copies) or same(s[i-1], x) && dp[i-1][j] (one more copy) |
| Base | dp[0][0] = true |
| Row 0 | at a star, dp[0][j] = dp[0][j-2] (a*b* matches the empty string) |
| Answer | dp[m][n] |
"One more copy" points at dp[i-1][j], the same pattern position, so it chains: any number of copies, one letter at a time.
By hand: aab against c*a*b
| s prefix \ p | ∅ | c | * | a | * | b |
|---|---|---|---|---|---|---|
"" |
✓ | · | ✓ | · | ✓ | · |
a |
· | · | · | ✓ | ✓ | · |
aa |
· | · | · | · | ✓ | · |
aab |
· | · | · | · | · | ✓ |
Solution in Java
import java.util.*;
public class Main {
static boolean isMatch(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 = 2; j <= n; j++)
if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char c = p.charAt(j - 1);
if (c == '*') {
char x = p.charAt(j - 2);
boolean one = x == '.' || x == s.charAt(i - 1);
dp[i][j] = dp[i][j - 2] || (one && dp[i - 1][j]);
} else {
boolean same = c == '.' || c == s.charAt(i - 1);
dp[i][j] = same && dp[i - 1][j - 1];
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(isMatch("aa", "a"));
System.out.println(isMatch("aa", "a*"));
System.out.println(isMatch("ab", ".*"));
System.out.println(isMatch("aab", "c*a*b"));
System.out.println(isMatch("mississippi", "mis*is*p*."));
System.out.println(isMatch("aaa", "a*a"));
System.out.println(isMatch("ab", ".*b"));
System.out.println(isMatch("", "a*"));
System.out.println(isMatch("", ""));
System.out.println(isMatch("a", ""));
System.out.println(isMatch("ab", ".*c"));
}
}
false
true
true
true
false
true
true
true
true
false
false
The 30 a's that timed out, and a 2,000-letter string against a 2,000-character pattern (four million cells):
import java.util.*;
public class Main {
static boolean isMatch(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 = 2; j <= n; j++)
if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char c = p.charAt(j - 1);
if (c == '*') {
char x = p.charAt(j - 2);
boolean one = x == '.' || x == s.charAt(i - 1);
dp[i][j] = dp[i][j - 2] || (one && dp[i - 1][j]);
} else {
boolean same = c == '.' || c == s.charAt(i - 1);
dp[i][j] = same && dp[i - 1][j - 1];
}
}
return dp[m][n];
}
public static void main(String[] args) {
String s = "a".repeat(30);
String p = "a*".repeat(15) + "c";
long t0 = System.nanoTime();
boolean ok = isMatch(s, p);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("30 letters: " + ok + ", " + ms + " ms");
String t = "ab".repeat(1000);
String q = "a*b.".repeat(499) + ".*" + "ab";
t0 = System.nanoTime();
ok = isMatch(t, q);
ms = (System.nanoTime() - t0) / 1000000;
System.out.println(t.length() + " x " + q.length() + ": " + ok + ", " + ms + " ms");
}
}
30 letters: false, 0 ms
2000 x 2000: true, 36 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Regular expression matching: dp[i][j] = the first i letters of s match the first j characters of p.
bool isMatch(const string& s, const string& p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int j = 2; j <= n; j++)
if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
bool one = p[j - 2] == '.' || p[j - 2] == s[i - 1];
dp[i][j] = dp[i][j - 2] || (one && dp[i - 1][j]); // zero copies OR one more copy
} else {
bool same = p[j - 1] == '.' || p[j - 1] == s[i - 1];
dp[i][j] = same && dp[i - 1][j - 1];
}
}
return dp[m][n];
}
int main() {
vector<pair<string, string>> t = {{"aa", "a"}, {"aa", "a*"}, {"ab", ".*"}, {"aab", "c*a*b"},
{"mississippi", "mis*is*p*."}, {"aaa", "a*a"}, {"ab", ".*b"}, {"", "a*"}, {"", ""}, {"a", ""}, {"ab", ".*c"}};
for (auto& [s, p] : t) cout << boolalpha << isMatch(s, p) << "\n";
}
false
true
true
true
false
true
true
true
true
false
false
The same solution in Python
# Regular expression matching: dp[i][j] = the first i letters of s match the first j characters of p.
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):
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] == "*":
one = p[j - 2] in (".", s[i - 1])
dp[i][j] = dp[i][j - 2] or (one and dp[i - 1][j]) # zero copies OR one more copy
else:
dp[i][j] = p[j - 1] in (".", s[i - 1]) and dp[i - 1][j - 1]
return dp[m][n]
tests = [("aa", "a"), ("aa", "a*"), ("ab", ".*"), ("aab", "c*a*b"), ("mississippi", "mis*is*p*."),
("aaa", "a*a"), ("ab", ".*b"), ("", "a*"), ("", ""), ("a", ""), ("ab", ".*c")]
for s, p in tests:
print(is_match(s, p))
False
True
True
True
False
True
True
True
True
False
False
Three real bugs
Bug 1: row 0 never filled.
import java.util.*;
public class Main {
static boolean isMatch(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 = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char c = p.charAt(j - 1);
if (c == '*') {
char x = p.charAt(j - 2);
boolean one = x == '.' || x == s.charAt(i - 1);
dp[i][j] = dp[i][j - 2] || (one && dp[i - 1][j]);
} else {
boolean same = c == '.' || c == s.charAt(i - 1);
dp[i][j] = same && dp[i - 1][j - 1];
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(isMatch("", "a*"));
System.out.println(isMatch("aab", "c*a*b"));
}
}
false
false
Both should be true: without row 0, c* (or a*) can never match nothing at the start.
Bug 2: no zero-copies case.
import java.util.*;
public class Main {
static boolean isMatch(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 = 2; j <= n; j++)
if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char c = p.charAt(j - 1);
if (c == '*') {
char x = p.charAt(j - 2);
boolean one = x == '.' || x == s.charAt(i - 1);
dp[i][j] = one && (dp[i - 1][j] || dp[i - 1][j - 2]);
} else {
boolean same = c == '.' || c == s.charAt(i - 1);
dp[i][j] = same && dp[i - 1][j - 1];
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(isMatch("ab", "ac*b"));
System.out.println(isMatch("aab", "c*a*b"));
}
}
false
true
false for ab against ac*b is wrong: c* must match zero c's in the middle. c*a*b still passes because row 0 covers zero copies at the very start, so a quick test can miss this bug.
Bug 3: an m × n table.
import java.util.*;
public class Main {
static boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m][n];
dp[0][0] = true;
for (int j = 2; j <= n; j++)
if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char c = p.charAt(j - 1);
if (c == '*') {
char x = p.charAt(j - 2);
boolean one = x == '.' || x == s.charAt(i - 1);
dp[i][j] = dp[i][j - 2] || (one && dp[i - 1][j]);
} else {
boolean same = c == '.' || c == s.charAt(i - 1);
dp[i][j] = same && dp[i - 1][j - 1];
}
}
return dp[m][n];
}
public static void main(String[] args) {
System.out.println(isMatch("aa", "a*"));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
at Main.isMatch(Main.java:9)
at Main.main(Main.java:25)
dp[i][j] is about prefixes, so i runs to m and j to n: the table needs (m + 1) × (n + 1) cells.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Greedy star | O(m + n) | O(1) | fast but wrong |
| Both choices, no memo | exponential | O(m + n) stack | 30 a's: Time Limit Exceeded |
Top-down memo on (i, j) |
O(m × n) | O(m × n) | same answers |
| Bottom-up table | O(m × n) | O(m × n), two rows: O(n) | 2,000 × 2,000: ~40 ms |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Greedy star | false for (aaa, a*a) |
the star ate too much | try zero copies OR one more |
| No row 0 | false for ("", a*) |
x* can match nothing |
dp[0][j] = dp[0][j-2] at stars |
| No zero-copies case | false for (ab, ac*b) |
a star can be empty | dp[i][j-2] \|\| ... |
new boolean[m][n] |
ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2 |
the empty prefix needs a row and a column | [m + 1][n + 1] |
Treating * as its own wildcard |
wrong answers | in regex * repeats the previous char (in wildcard matching it doesn't) |
read the problem |
Partial match (find instead of matches) |
true for (ab, a) |
must cover the whole string | answer dp[m][n] only |
Mini project: a tiny grep
Read a pattern and a list of lines; print the lines the pattern matches fully. Then add + (one or more: x+ = xx*) and ? (zero or one) by rewriting them before matching. Compare your results with Java's s.matches(p) on random tests.
Practice
1. Wildcard Matching (LeetCode 44). ? = any one letter, * = any run of letters (not tied to the previous character).
2. Interleaving String (LeetCode 97). Is c an interleaving of a and b? ok[i][j] over the prefixes of a and b.
Solutions
In wildcard matching the star's two options are dp[i][j-1] (match nothing) and dp[i-1][j] (eat one more letter).
import java.util.*;
public class Main {
// Wildcard Matching (LeetCode 44): '?' = any one letter, '*' = any run of letters (even empty).
static boolean wildcard(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++)
if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char c = p.charAt(j - 1);
if (c == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; // star matches nothing, or one more letter
else dp[i][j] = (c == '?' || c == s.charAt(i - 1)) && dp[i - 1][j - 1];
}
return dp[m][n];
}
// Interleaving String (LeetCode 97): ok[i][j] = s3's first i + j letters interleave a's first i and b's first j.
static boolean interleave(String a, String b, String c) {
if (a.length() + b.length() != c.length()) return false;
boolean[][] ok = new boolean[a.length() + 1][b.length() + 1];
ok[0][0] = true;
for (int i = 0; i <= a.length(); i++)
for (int j = 0; j <= b.length(); j++) {
if (i > 0 && a.charAt(i - 1) == c.charAt(i + j - 1) && ok[i - 1][j]) ok[i][j] = true;
if (j > 0 && b.charAt(j - 1) == c.charAt(i + j - 1) && ok[i][j - 1]) ok[i][j] = true;
}
return ok[a.length()][b.length()];
}
public static void main(String[] args) {
System.out.println(wildcard("aa", "a"));
System.out.println(wildcard("aa", "*"));
System.out.println(wildcard("adceb", "*a*b"));
System.out.println(wildcard("acdcb", "a*c?b"));
System.out.println(interleave("aabcc", "dbbca", "aadbbcbcac"));
System.out.println(interleave("aabcc", "dbbca", "aadbbbaccc"));
}
}
false
true
true
false
true
false
3. Distinct Subsequences (LeetCode 115). Count how many times t appears as a subsequence of s: dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0).
4. Draw the table for (aa, a*). Row 0: ✓ · ✓. Row a: · ✓ ✓. Row aa: · · ✓. Answer ✓.
Quick quiz
Does aab match a.*b*? A) true B) false: b* needs a b C) false: . needs a letter D) it throws an exception
Answer
A) true. a matches a, .* takes ab, b* takes zero b's (or .* takes a and b* takes the b).
Interview questions
- Why does greedy fail? A star can't know how many letters to leave for the rest of the pattern.
- State and recurrence? Letter/dot: diagonal. Star:
dp[i][j-2] || (match(s[i-1], p[j-2]) && dp[i-1][j]). - Why does "one more copy" look at
dp[i-1][j]and notdp[i-1][j-2]? Staying on the star lets it eat any number of letters, one per row. - Why does row 0 need filling? Patterns like
a*b*match the empty string. - Complexity? O(m × n) time; O(m × n) space, or O(n) with two rows.
- Regex vs wildcard matching? In regex,
*repeats the previous character; in wildcard matching,*is any run of letters on its own. - Top-down or bottom-up? Both are O(m × n); top-down memo is often quicker to write from the recursion.
Glossary
| Term | Meaning |
|---|---|
| Regular expression | A pattern describing strings |
. |
Any one character |
x* |
Zero or more copies of x |
| Full match | The pattern covers the whole string |
| Greedy | Take as much as possible, never give back |
| State | (i, j): prefixes of s and p |
| Recurrence | diagonal for letters; zero OR one more for stars |
| Base case | dp[0][0] = true, row 0 at stars |
| Memoization | Caching match(i, j) |
| Wildcard matching | ? and a free-standing * |
Summary
- A greedy star takes too much; trying both choices is right but exponential.
dp[i][j]: letter or dot →same && dp[i-1][j-1]; star →dp[i][j-2] || (same && dp[i-1][j]).dp[0][0] = true, and row 0 copies from two columns back at every star.- O(m × n) time, O(n) space with two rows.
- Next episode: burst balloons, DP over intervals, where the trick is the last balloon to burst.