10. Regular Expression Matching

This problem asks to implement regular expression matching with support for '.' (matches any single character) and '*' (matches zero or more of the preceding element). The matching must cover the entire input string.

Approach: Dynamic Programming

The most efficient approach is using dynamic programming. We create a 2D boolean array dp where dp[i][j] is true if the first i characters of the input string s match the first j characters of the pattern p, and false otherwise.

The base cases are:

• dp[0][0] = true (empty string matches empty pattern)
• dp[i][0] = false for i > 0 (non-empty string can't match empty pattern)
• dp[0][j] needs careful consideration based on p (handled in the code)

The recursive relation is built based on the character at p[j-1]:

1. If p[j-1] is not '*':

   • If s[i-1] and p[j-1] match (either equal or p[j-1] is '.'), then dp[i][j] = dp[i-1][j-1] (match the current characters and recursively check the rest).
   • Otherwise, dp[i][j] = false (no match).

2. If p[j-1] is '*':

   • It means we can have zero or more occurrences of p[j-2].
   • dp[i][j] = dp[i][j-2] (ignore the p[j-1] and p[j-2]).
   • If s[i-1] and p[j-2] match, then we can also consider matching one or more occurrences of p[j-2]: dp[i][j] = dp[i][j] || dp[i-1][j].

The final result is dp[m][n], where m and n are the lengths of s and p respectively.

Time and Space Complexity

• Time Complexity: O(m*n), where m and n are the lengths of the input string and pattern respectively. We iterate through the dp array.
• Space Complexity: O(m*n) to store the dp array. This can be optimized to O(n) using space optimization techniques but is not implemented here for clarity.

Code in Different Languages

Python

class 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
        for j in range(1, 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]

Java

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 = 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++) {
                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];
    }
}

(Other languages like C++, JavaScript, Go, etc., would follow a similar structure, adapting syntax and data structures as needed.)

This dynamic programming solution provides an efficient way to solve the Regular Expression Matching problem. Remember that while space optimization is possible, the provided solutions prioritize clarity and readability.