Regular Expression Matching

hard string dp recursion

Problem

Match input string s against pattern p that supports two metacharacters: '.' matches any single character, and '*' matches zero or more of the preceding element. The pattern must match the entire input string.

Let dp[i][j] be true if s[..i] matches p[..j]. The interesting case is when p[j−1] is '*': dp[i][j] is true if you either ignore the "x*" pair (dp[i][j−2]) or x matches s[i−1] and dp[i−1][j] is true (consume one more character).

Inputs = "aab", p = "c*a*b"

Outputtrue

"c*" matches 0 c's, "a*" matches 2 a's, then 'b' matches 'b'.

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(2, n + 1):
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                dp[i][j] = dp[i][j - 2]
                if p[j - 2] == "." or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            elif p[j - 1] == "." or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

function isMatch(s, p) {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 2; j <= n; j++) if (p[j - 1] === "*") dp[0][j] = dp[0][j - 2];
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; 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[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 = 2; 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++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

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

Explanation

We fill a 2D table where dp[i][j] is true when the first i characters of the string s are matched by the first j characters of the pattern p. Building it cell by cell lets us reuse smaller matches instead of re-scanning.

The base case is dp[0][0] = true (empty matches empty). We also pre-fill the top row for patterns like "a*b*" that can match the empty string by treating each x* as zero copies.

The tricky character is *. When p[j-1] is *, we have two ways to be true: use it zero times, which skips the x* pair via dp[i][j-2]; or, if the preceding pattern char (. or the same letter) matches s[i-1], consume one more character via dp[i-1][j].

For an ordinary character or ., it simply has to match the current string character, and then the answer carries over from dp[i-1][j-1].

Example: s = "aab", p = "c*a*b". Here c* matches zero c's, a* matches the two a's, and b matches b, so dp[3][5] is true.

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