String Matching DP: Wildcards and Regular Expressions

Regular Expression Matching (LeetCode 10)

Supports . (match any single character) and * (match zero or more of the preceding element).

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    // dp[i][j]: whether s[0..i-1] matches p[0..j-1]
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    
    // Base Case: p like "a*b*c*" can match an empty string s
    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 sc = s.charAt(i - 1), pc = p.charAt(j - 1);
            if (pc == '*') {
                // Choice 1: '*' matches zero of the preceding character
                dp[i][j] = dp[i][j - 2];
                // Choice 2: '*' matches one or more if precedes matches current sc
                char prevP = p.charAt(j - 2);
                if (prevP == '.' || prevP == sc) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            } else {
                // Direct character match
                if (pc == '.' || pc == sc) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }
    return dp[m][n];
}

Wildcard Matching (LeetCode 44)

Supports ? (match any single character) and * (match any sequence of characters, including empty).

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;
    
    // Base Case: '*' can match empty string
    for (int j = 1; j <= n; j++) {
        if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char sc = s.charAt(i - 1), pc = p.charAt(j - 1);
            if (pc == '*') {
                // '*' matches empty string -> dp[i][j-1]
                // '*' matches current s[i-1] -> dp[i-1][j]
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else {
                if (pc == '?' || pc == sc) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }
    return dp[m][n];
}

Side-by-Side Comparison

Solution Insights

• Both problems leverage 2D Dynamic Programming, where dp[i][j] maps the prefix of s and p.
• Initialization of dp[0][j] is critical: it represents whether the pattern can collapse into an empty string.
• When handling *, consider two main branches:
  1. Zero items: The pattern char (and its preceding char in regex) effectively disappears.
  2. One or more items: The current string char is swallowed by the *, and we continue evaluating from dp[i-1][j]. 筋