Regular Expression Matching

NeetCode: Regular Expression Matching · LeetCode: 10. Regular Expression Matching · Difficulty: Hard

Given a string s and a pattern p, return true if p matches the entire string. . matches any single character, and * matches zero or more of the element right before it.

Example

Text

Input:  s = "aa",          p = "a"            Output: false
Input:  s = "aa",          p = "a*"           Output: true
Input:  s = "ab",          p = ".*"           Output: true
Input:  s = "aab",         p = "c*a*b"        Output: true
Input:  s = "mississippi", p = "mis*is*p*."   Output: false

Brute force: plain recursion on suffixes

Let m(i, j) say whether s[i..] matches p[j..]. If the pattern is used up, the string must be too. Otherwise check whether the first characters match (p[j] is . or equals s[i], and s is not empty). If the next pattern character is *, there are two choices: skip the starred element entirely (m(i, j + 2)) or, if the first characters match, consume one character of s and stay on the same starred element (m(i + 1, j)). Without a star, both must advance together. The star's two-way branching repeats many (i, j) pairs.

Java

class Solution {
    public boolean isMatch(String s, String p) {
        return m(s, p, 0, 0);
    }

    private boolean m(String s, String p, int i, 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 m(s, p, i, j + 2) || (first && m(s, p, i + 1, j));
        }
        return first && m(s, p, i + 1, j + 1);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isMatch("aa", "a"));
        System.out.println(s.isMatch("aa", "a*"));
        System.out.println(s.isMatch("ab", ".*"));
        System.out.println(s.isMatch("aab", "c*a*b"));
        System.out.println(s.isMatch("mississippi", "mis*is*p*."));
        System.out.println(s.isMatch("", "a*"));
    }
}

Output

false
true
true
true
false
true

Time: exponential in the worst case (for example s = "aaaa...a", p = "a*a*a*...b"). Space: O(m + n).

Better: memoise (i, j)

The answer to m(i, j) depends only on the two suffix start positions, so there are at most (m + 1) * (n + 1) distinct calls. Caching each answer makes every state cost O(1). The cache is a Boolean[][]: Boolean is the object form of boolean, so an unfilled entry is null and means "not computed yet".

A * after p[j] means zero or more copies of p[j]. Either use zero copies (skip the pair: m(i, j + 2)), or use one more copy if s[i] matches p[j] (consume one character and stay on the same pair: m(i + 1, j)).

Java

class Solution {
    public boolean isMatch(String s, String p) {
        Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
        return m(s, p, 0, 0, memo);
    }

    private boolean m(String s, String p, int i, int j, Boolean[][] memo) {
        if (memo[i][j] != null) return memo[i][j];
        boolean ans;
        if (j == p.length()) {
            ans = i == s.length();
        } else {
            boolean first = i < s.length() && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i));
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                ans = m(s, p, i, j + 2, memo) || (first && m(s, p, i + 1, j, memo));
            } else {
                ans = first && m(s, p, i + 1, j + 1, memo);
            }
        }
        memo[i][j] = ans;
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isMatch("aa", "a"));
        System.out.println(s.isMatch("aa", "a*"));
        System.out.println(s.isMatch("ab", ".*"));
        System.out.println(s.isMatch("aab", "c*a*b"));
        System.out.println(s.isMatch("mississippi", "mis*is*p*."));
        System.out.println(s.isMatch("", "a*"));
    }
}

Output

false
true
true
true
false
true

Time: O(m · n). Space: O(m · n).

Optimal: bottom-up table with rolling rows

Let dp[i][j] be whether s[i..] matches p[j..], with dp[m][n] = true. Fill i from m down to 0 and j from n down to 0 using the same transitions: dp[i][j+2], dp[i+1][j], dp[i+1][j+1]. Each cell reads only the current row and the next row, so two rows of length n + 1 are enough. After each row, the two array references are swapped.

Java

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        // next = row i + 1, cur = row i; each holds dp[.][0..n]
        boolean[] next = new boolean[n + 1];
        boolean[] cur = new boolean[n + 1];
        for (int i = m; i >= 0; i--) {
            cur[n] = i == m;
            for (int j = n - 1; j >= 0; j--) {
                boolean first = i < m && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i));
                if (j + 1 < n && p.charAt(j + 1) == '*') {
                    cur[j] = cur[j + 2] || (first && next[j]);
                } else {
                    cur[j] = first && next[j + 1];
                }
            }
            boolean[] tmp = cur;
            cur = next;
            next = tmp;
        }
        return next[0];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isMatch("aa", "a"));
        System.out.println(s.isMatch("aa", "a*"));
        System.out.println(s.isMatch("ab", ".*"));
        System.out.println(s.isMatch("aab", "c*a*b"));
        System.out.println(s.isMatch("mississippi", "mis*is*p*."));
        System.out.println(s.isMatch("", "a*"));
    }
}

Output

false
true
true
true
false
true

Time: O(m · n). Space: O(n).

Edge cases

An empty string can still match a pattern such as a* or a*b*; the skip branch handles it.
first must check i < s.length() before calling charAt, which throws StringIndexOutOfBoundsException past the end.
A leading * does not occur in valid input, so p.charAt(j + 1) == '*' always refers to an element that exists.
The rolling-row version reuses the array that held row i + 1 as row i - 1. Every entry of cur is written before it is read, so stale values do not matter.

How to explain it in an interview

Start with plain recursion on suffixes (i, j); the * branches two ways, so it is exponential.
Key insight: the result depends only on (i, j), so it can be cached; and x* is a unit that is either skipped or consumes one more character.
Steps: base case (pattern used up means i == s.length()); compute first (string not empty and p[j] is . or equals s[i]); if p[j+1] == '*', skip the pair or (first and advance i, stay on j); otherwise first and advance both.
Complexity: O(m · n) time; O(m · n) space memoised, O(n) with rolling rows.