Regular Expression matching [DP]

XXX.Regular Expression Matching

Dynamic Programming

Problem Statement:

Implement a regular expression matching function that supports the special characters:

• '.' which matches any single character.
• '*' which matches zero or more of the preceding element.

The function should return true if the given string s matches the pattern p, and false otherwise.

Algorithm:

1. Initialize a 2D boolean DP table dp, where dp[i][j] represents if the first i characters of s match the first j characters of p.
2. Set dp[0][0] = true, as an empty string matches an empty pattern.
3. Handle the case of '*' in the pattern:
   • If p[j-1] == '*', then check two cases:
     • Ignore the '*' and the preceding character (dp[i][j-2]).
     • If the preceding character matches, use the '*' to match multiple characters (dp[i-1][j]).
4. Iterate through the DP table to compute values based on the above rules.
5. Return dp[s.length()][p.length()] as the result.

Complexity:

Time: O(m × n), where m is the length of s and n is the length of p. | Space: O(m × n), for the DP table.

Java Implementation:

public boolean isMatch(String s, String p) {
    // Initialize the DP table where dp[i][j] indicates if s[0..i-1] matches p[0..j-1]
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    
    // Base case: Empty string matches empty pattern
    dp[0][0] = true;
    
    // Fill the first row for patterns with '*' that can match an empty string
    for (int j = 1; j < dp[0].length; j++) 
        if (p.charAt(j - 1) == '*') 
            dp[0][j] = dp[0][j - 2];  // '*' can represent zero occurrences of the preceding character
    
    // Fill the DP table
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            // Case 1: Characters match or pattern has '.', copy the diagonal value
            if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') 
                dp[i][j] = dp[i - 1][j - 1];
            // Case 2: Pattern has '*'
            else if (p.charAt(j - 1) == '*') {
                // Option 1: Ignore '*' and preceding character
                if (dp[i][j - 2]) 
                    dp[i][j] = true;
                // Option 2: Use '*' to match current character
                else if (p.charAt(j - 2) == '.' || s.charAt(i - 1) == p.charAt(j - 2)) 
                    dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // Final result is whether the entire string matches the pattern
    return dp[s.length()][p.length()];
}