SyntaxPilot
Courses/DSA and Coding Problems/Lesson 73
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 73 of 90

Regular expression matching (hard)

queued

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 of x; x may 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 first i letters of s and the first j characters of p.
  • Prefix: the first i characters; the empty prefix is i = 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 match a*b*.
  • Memoization: the top-down alternative: cache match(i, j) in a Boolean[][].

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 × 32 pairs 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

  1. Why does greedy fail? A star can't know how many letters to leave for the rest of the pattern.
  2. State and recurrence? Letter/dot: diagonal. Star: dp[i][j-2] || (match(s[i-1], p[j-2]) && dp[i-1][j]).
  3. Why does "one more copy" look at dp[i-1][j] and not dp[i-1][j-2]? Staying on the star lets it eat any number of letters, one per row.
  4. Why does row 0 need filling? Patterns like a*b* match the empty string.
  5. Complexity? O(m × n) time; O(m × n) space, or O(n) with two rows.
  6. Regex vs wildcard matching? In regex, * repeats the previous character; in wildcard matching, * is any run of letters on its own.
  7. 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.