Regex Pattern

Leetcode 10 vs Leetcode 44

O(m x n) time and space. dp[m,n] = true, dp[m, n-1] = false

Non cached version ⇒

• Time: exponential, roughly O(2^(m+n)) in the worst case because * can create two recursive branches.
• Space: O(m+n) for the recursion stack. There is no memo table.

LC 10 — Regular Expression Matching

var isMatch = function(s, p) {
 
    const dfs = (i, j) => {
        // Both finished
        if (i >= s.length && j >= p.length) {
            return true;
        }
 
        // Pattern finished
        if (j >= p.length) {
            return false;
        }
 
        const match =
            i < s.length &&
            (s[i] === p[j] || p[j] === ".");
 
        // Next char is *
        if (j + 1 < p.length && p[j + 1] === "*") {
            return (
                dfs(i, j + 2) ||             // don't use *
                (match && dfs(i + 1, j))     // use *
            );
        }
 
        // Normal match
        if (match) {
            return dfs(i + 1, j + 1);
        }
 
        return false;
    };
 
    return dfs(0, 0);
};

LC 44 — Wildcard Matching

 
var isMatch = function(s, p) {
 
    const dfs = (i, j) => {
        if (i >= s.length && j >= p.length) {
            return true;
        }
 
        if (j >= p.length) {
            return false;
        }
 
        if (p[j] === "*") {
            return (
                dfs(i, j + 1) ||
                (i < s.length && dfs(i + 1, j))
            );
        }
 
        const match =
            i < s.length &&
            (s[i] === p[j] || p[j] === "?");
 
        if (match) {
            return dfs(i + 1, j + 1);
        }
 
        return false;
    };
 
    return dfs(0, 0);
};

Why does LC10 require firstMatch when using *?

Because:

s = "bbb"
p = "a*"

a* cannot consume a b.

But in LC44:

s = "bbb"
p = "*"

* can consume any character, so no firstMatch check is necessary.

And the other difference is just:

// LC 10
p[j] === '.'
 
// LC 44
p[j] === '?'

So if you can write LC10 from memory now, LC44 is essentially LC10 with a simpler *.