Regular expresion matching

10.Regular Expression Matching

String

Dynamic Programming

Recursion

Problem Statement:

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element.

Example:

Input:

s = "aa", p = "a*"

→

Output:

true

Algorithm:

1. Create DP table s+1 by p+1
2. Initialize first row for empty string cases
3. Handle direct matches and dots
4. Handle star pattern with previous char

Complexity:

Time: O(mn) | Space: O(mn)

Java Solution:

public boolean isMatch(String s, String p) {
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    
    // Empty pattern matches empty string
    dp[0][0] = true;
    
    // Initialize first row - empty string matching with pattern
    for (int j = 1; j < dp[0].length; j++) 
        if (p.charAt(j - 1) == '*') 
            dp[0][j] = dp[0][j - 2];  // Skip the pattern and its star
    
    // Fill DP table
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            
            // Direct match or dot match
            if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                dp[i][j] = dp[i - 1][j - 1];
                    
            } // Star pattern
            else if (p.charAt(j - 1) == '*') {
                // Zero occurrence of previous char
                if (dp[i][j - 2]) 
                    dp[i][j] = true;
                // Multiple occurrences if previous char matches or is dot
                else if (p.charAt(j - 2) == '.' || s.charAt(i - 1) == p.charAt(j - 2)) 
                    dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[s.length()][p.length()];
}

Python Solution:

def isMatch(self, s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    # Handle patterns that can match empty string
    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]
    
    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '.' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                dp[i][j] = dp[i][j-2]  # Zero occurrence
                if p[j-2] == '.' or p[j-2] == s[i-1]:
                    dp[i][j] |= dp[i-1][j]  # Multiple occurrences
                    
    return dp[m][n]

C++ Solution:

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vectorbool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        
        // Handle patterns that can match empty string
        for(int j = 1; 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] == '.' || p[j-1] == s[i-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } 
                else if(p[j-1] == '*') {
                    dp[i][j] = dp[i][j-2];  // Zero occurrence
                    if(p[j-2] == '.' || p[j-2] == s[i-1]) {
                        dp[i][j] = dp[i][j] || dp[i-1][j];  // Multiple occurrences
                    }
                }
            }
        }
        
        return dp[m][n];
    }
};