10. Regular Expression Matching (Hard)

Problem

Implement regular expression matching with support for:

• ., matches any single character.
• *, matches zero or more of the preceding element.

The match must cover the entire input string (not partial).

Example

• s = "aa", p = "a" → false
• s = "aa", p = "a*" → true
• s = "ab", p = ".*" → true
• s = "mississippi", p = "mis*is*p*." → false

LeetCode 10 · Link · Hard

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Recursive

Match character-by-character, special-casing *.

Python

def is_match(s, p):
    def match(i, j):                                           # L1: define recursive helper
        if j == len(p):                                        # L2: O(1) base case check
            return i == len(s)
        first = i < len(s) and (p[j] == '.' or p[j] == s[i]) # L3: O(1) single-char match check
        if j + 1 < len(p) and p[j + 1] == '*':               # L4: O(1) check for '*'
            # zero copies, or one more copy
            return match(i, j + 2) or (first and match(i + 1, j))  # L5: two recursive calls
        return first and match(i + 1, j + 1)                  # L6: one recursive call
    return match(0, 0)

TypeScript

function isMatch(s: string, p: string): boolean {
    function match(i: number, j: number): boolean {             // L1: define recursive helper
        if (j === p.length) return i === s.length;              // L2: O(1) base case check
        const first = i < s.length && (p[j] === '.' || p[j] === s[i]);  // L3: O(1) single-char match
        if (j + 1 < p.length && p[j + 1] === '*')             // L4: O(1) check for '*'
            return match(i, j + 2) || (first && match(i + 1, j));       // L5: two recursive calls
        return first && match(i + 1, j + 1);                   // L6: one recursive call
    }
    return match(0, 0);
}

Swift

final class Solution {
    func isMatch(_ s: String, _ p: String) -> Bool {
        let text = Array(s), pattern = Array(p)
        func solve(_ i: Int, _ j: Int) -> Bool {
            if j == pattern.count { return i == text.count }
            let first = i < text.count && (pattern[j] == "." || pattern[j] == text[i])
            if j + 1 < pattern.count && pattern[j + 1] == "*" {
                return solve(i, j + 2) || (first && solve(i + 1, j))
            }
            return first && solve(i + 1, j + 1)
        }
        return solve(0, 0)
    }
}

Where the time goes, line by line

Variables: m = len(s), n = len(p).

Line	Per-call cost	Times executed	Contribution
L1-L4 (setup + checks)	$O(1)$	per call	$O(1)$ each
L5 (two recursive branches on ’*’)	$O(1)$ work + 2 calls	up to $O(2^{m+n})$ calls total	$O(2^{m+n})$ ← dominates
L6 (one recursive branch)	$O(1)$ work + 1 call	per call	$O(2^{m+n})$ same tree

The exponential blowup comes from the * branch at L5: each * pair can spawn two calls. Without memoization the same (i, j) pair is recomputed many times.

Complexity

• Time: $O(2^{m+n})$ worst case due to overlapping subproblems (driven by L5 double-branching).
• Space: $O(m + n)$ recursion depth.

Approach 2: Top-down memoized (canonical)

Cache by (i, j).

Python

from functools import lru_cache

def is_match(s, p):
    @lru_cache(maxsize=None)                                   # L1: O(1) cache decorator setup
    def match(i, j):
        if j == len(p):                                        # L2: O(1) base case
            return i == len(s)
        first = i < len(s) and (p[j] == '.' or p[j] == s[i]) # L3: O(1) char match check
        if j + 1 < len(p) and p[j + 1] == '*':               # L4: O(1) '*' check
            return match(i, j + 2) or (first and match(i + 1, j))  # L5: O(1) with cache
        return first and match(i + 1, j + 1)                  # L6: O(1) with cache
    return match(0, 0)

TypeScript

function isMatch(s: string, p: string): boolean {
    const memo: Map<string, boolean> = new Map();
    function match(i: number, j: number): boolean {
        const key = `${i},${j}`;
        if (memo.has(key)) return memo.get(key)!;              // L1: O(1) cache lookup
        if (j === p.length) return i === s.length;             // L2: O(1) base case
        const first = i < s.length && (p[j] === '.' || p[j] === s[i]);  // L3: O(1) char match
        let result: boolean;
        if (j + 1 < p.length && p[j + 1] === '*')             // L4: O(1) '*' check
            result = match(i, j + 2) || (first && match(i + 1, j));     // L5: O(1) with cache
        else
            result = first && match(i + 1, j + 1);            // L6: O(1) with cache
        memo.set(key, result);
        return result;
    }
    return match(0, 0);
}

Where the time goes, line by line

Variables: m = len(s), n = len(p).

Line	Per-call cost	Times executed	Contribution
L1 (lru_cache)	$O(1)$	1	$O(1)$
L2-L4 (checks)	$O(1)$	once per unique (i,j)	$O(m · n)$ total
L5, L6 (recursive calls)	$O(1)$ per call (cache hit after first)	at most m · n unique states	$O(m · n)$ ← dominates

With memoization, each unique (i, j) pair is computed exactly once. There are (m+1) * (n+1) such pairs, each doing $O(1)$ work.

Complexity

• Time: $O(m · n)$, driven by L5/L6 over all unique (i,j) states.
• Space: $O(m · n)$ for the memo table.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isMatch(_ s: String, _ p: String) -> Bool {
        let text = Array(s), pattern = Array(p)
        var memo: [String: Bool] = [:]
        func solve(_ i: Int, _ j: Int) -> Bool {
            let key = "\(i):\(j)"
            if let cached = memo[key] { return cached }
            if j == pattern.count { return i == text.count }
            let first = i < text.count && (pattern[j] == "." || pattern[j] == text[i])
            let answer = j + 1 < pattern.count && pattern[j + 1] == "*"
                ? solve(i, j + 2) || (first && solve(i + 1, j))
                : first && solve(i + 1, j + 1)
            memo[key] = answer
            return answer
        }
        return solve(0, 0)
    }
}

Approach 3: Bottom-up 2-D DP

dp[i][j] = does s[:i] match p[:j]?

Python

def is_match(s, p):
    m, n = len(s), len(p)                                  # L1: O(1)
    dp = [[False] * (n + 1) for _ in range(m + 1)]        # L2: O(m*n) table init
    dp[0][0] = True                                        # L3: O(1) base case

    # Empty string vs. patterns like "a*", "a*b*"
    for j in range(1, n + 1):                             # L4: O(n) init loop
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):                             # L5: outer loop O(m)
        for j in range(1, n + 1):                         # L6: inner loop O(n)
            if p[j - 1] == '*':                           # L7: O(1) check
                # zero occurrences
                dp[i][j] = dp[i][j - 2]                  # L8: O(1)
                # one or more: previous char matches current s
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:  # L9: O(1)
                    dp[i][j] = dp[i][j] or dp[i - 1][j]      # L10: O(1)
            else:
                if p[j - 1] == '.' or p[j - 1] == s[i - 1]:  # L11: O(1)
                    dp[i][j] = dp[i - 1][j - 1]               # L12: O(1)
    return dp[m][n]

TypeScript

function isMatch(s: string, p: string): boolean {
    const m = s.length, n = p.length;                                         // L1: O(1)
    const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
        new Array(n + 1).fill(false));                                         // L2: O(m*n) table init
    dp[0][0] = true;                                                           // L3: O(1) base case
    for (let j = 1; j <= n; j++)                                               // L4: O(n) init loop
        if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
    for (let i = 1; i <= m; i++) {                                             // L5: outer loop O(m)
        for (let j = 1; j <= n; j++) {                                         // L6: inner loop O(n)
            if (p[j - 1] === '*') {                                            // L7: O(1) check
                dp[i][j] = dp[i][j - 2];                                      // L8: zero occurrences
                if (p[j - 2] === '.' || p[j - 2] === s[i - 1])               // L9: O(1)
                    dp[i][j] = dp[i][j] || dp[i - 1][j];                     // L10: O(1)
            } else {
                if (p[j - 1] === '.' || p[j - 1] === s[i - 1])               // L11: O(1)
                    dp[i][j] = dp[i - 1][j - 1];                              // L12: O(1)
            }
        }
    }
    return dp[m][n];
}

Where the time goes, line by line

Variables: m = len(s), n = len(p).

Line	Per-call cost	Times executed	Contribution
L1-L3 (init)	$O(1)$ or $O(m·n)$	1	$O(m · n)$
L4 (base-case loop)	$O(1)$	n	$O(n)$
L5+L6 (double loop)	$O(1)$ body	m · n	$O(m · n)$ ← dominates
L7-L12 (table fills)	$O(1)$	once each	included above

Every cell is filled in $O(1)$ with a constant number of table lookups. The double loop at L5/L6 visits all m * n cells exactly once.

Complexity

• Time: $O(m · n)$, driven by L5/L6 (the full double loop over all DP cells).
• Space: $O(m · n)$ for the DP table.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isMatch(_ s: String, _ p: String) -> Bool {
        let text = Array(s), pattern = Array(p)
        var dp = Array(repeating: Array(repeating: false, count: pattern.count + 1), count: text.count + 1)
        dp[text.count][pattern.count] = true
        for i in stride(from: text.count, through: 0, by: -1) {
            if pattern.isEmpty { continue }
            for j in stride(from: pattern.count - 1, through: 0, by: -1) {
                let first = i < text.count && (pattern[j] == "." || pattern[j] == text[i])
                if j + 1 < pattern.count && pattern[j + 1] == "*" {
                    dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j])
                } else if first {
                    dp[i][j] = dp[i + 1][j + 1]
                }
            }
        }
        return dp[0][0]
    }
}

Summary

Approach	Time	Space
Naive recursion	$O(2^{m+n})$	$O(m + n)$
Top-down memoized	$O(m · n)$	$O(m · n)$
Bottom-up 2-D DP	$O(m · n)$	$O(m · n)$

This problem rewards memorization, the recurrence is fiddly and the edge cases around * at the start are easy to bungle. Interview-standard answer is memoized recursion for clarity.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_010.py and run.
# Uses the canonical implementation (Approach 2: top-down memoized).

from functools import lru_cache

def is_match(s, p):
    @lru_cache(maxsize=None)
    def match(i, j):
        if j == len(p):
            return i == len(s)
        first = i < len(s) and (p[j] == '.' or p[j] == s[i])
        if j + 1 < len(p) and p[j + 1] == '*':
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)
    return match(0, 0)

def _run_tests():
    # problem statement examples
    assert is_match("aa", "a") == False
    assert is_match("aa", "a*") == True
    assert is_match("ab", ".*") == True
    assert is_match("mississippi", "mis*is*p*.") == False
    # edge: empty string vs empty pattern
    assert is_match("", "") == True
    # edge: empty string vs "a*" (zero occurrences)
    assert is_match("", "a*") == True
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function isMatch(s: string, p: string): boolean {
    const memo: Map<string, boolean> = new Map();
    function match(i: number, j: number): boolean {
        const key = `${i},${j}`;
        if (memo.has(key)) return memo.get(key)!;
        if (j === p.length) return i === s.length;
        const first = i < s.length && (p[j] === '.' || p[j] === s[i]);
        let result: boolean;
        if (j + 1 < p.length && p[j + 1] === '*')
            result = match(i, j + 2) || (first && match(i + 1, j));
        else
            result = first && match(i + 1, j + 1);
        memo.set(key, result);
        return result;
    }
    return match(0, 0);
}

console.assert(isMatch("aa", "a") === false);
console.assert(isMatch("aa", "a*") === true);
console.assert(isMatch("ab", ".*") === true);
console.assert(isMatch("mississippi", "mis*is*p*.") === false);
console.assert(isMatch("", "") === true);
console.assert(isMatch("", "a*") === true);
console.log("all tests pass");

Related data structures

• Strings, regex over prefix lengths

Related concepts

• Constraint Search, pruned search tactics for problems where each choice must satisfy local and global constraints.
• Memoization, top-down caching tactics for preserving recursive clarity while avoiding repeated subproblem work.