Regular Expression Matching

HardDynamic Programming

Implement regular expression matching with support for '.' (any single character) and '*' (zero or more of the preceding element), matching the entire input.

Open problem

Constraints

1 <= s.length <= 20
1 <= p.length <= 20

2D DP over string and pattern

Time O(n * m)Space O(n * m)

dp[i][j] is whether the first i characters of s match the first j of p. A '*' can match zero occurrences (skip two pattern chars) or one more occurrence when the preceding pattern char matches s.

#include <bits/stdc++.h>
using namespace std;

bool isMatch(string s, string p) {
    int n = s.size(), m = p.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;
    for (int j = 1; j <= m; j++)
        if (p[j-1] == '*') dp[0][j] = dp[0][j-2];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2];
                if (p[j-2] == '.' || p[j-2] == s[i-1]) dp[i][j] = dp[i][j] || dp[i-1][j];
            } else if (p[j-1] == '.' || p[j-1] == s[i-1]) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    return dp[n][m];
}