10. Regular Expression Matching

dp[i][j] is whether s[:i] matches p[:j]. A '*' either drops the preceding pattern element (zero copies) or, if that element matches s[i-1], consumes one more character of s.

Definition

dp[i][j] = does s[:i] match p[:j]? Answer is dp[m][n].

Transitions

• If p[j-1] is a normal char or . matching s[i-1]: dp[i][j] = dp[i-1][j-1].
• If p[j-1] == '*':
  • zero copies of the preceding element: dp[i][j] = dp[i][j-2].
  • one more copy (only if p[j-2] matches s[i-1] or is .): dp[i][j] |= dp[i-1][j].

Base: dp[0][0] = True; and dp[0][j] handles patterns like a*b* matching empty.

Worked example

s = "aab", p = "c*a*b": c* matches zero c's, a* matches two a's, b matches b → true.

Complexity

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

class Solution {
    public 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 = 1; 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 pc = p.charAt(j - 1);
                if (pc == '*') {
                    dp[i][j] = dp[i][j - 2];
                    char prev = p.charAt(j - 2);
                    if (prev == '.' || prev == s.charAt(i - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else if (pc == '.' || pc == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}