Regular Expression Matching hard

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.

The matching should cover the entire input string (not partial).

Example 1

Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' zero times, it matches the input string "aa".

Example 2

Input: s = "aab", p = "cab" Output: true Explanation: 'c*' allows 0 occurrences of 'c'. 'a*' allows 0 or more occurrences of 'a'. Thus, "aab" can be matched.

Steps and Explanation

This problem can be solved efficiently using dynamic programming. We create a table dp where dp[i][j] represents whether the first i characters of s match the first j characters of p.

We iterate through the table, filling it based on the following rules:

1. Base Case: dp[0][0] = true (empty string matches empty pattern).

2. Pattern starts with '*': If p[j-1] is '*', we have two possibilities:

   • The '*' matches zero occurrences of the preceding element: dp[i][j] = dp[i][j-2]
   • The '*' matches one or more occurrences: dp[i][j] = dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')

3. Pattern doesn't start with '*':

   • If s[i-1] matches p[j-1] (either equal or p[j-1] is '.'), then dp[i][j] = dp[i-1][j-1]
   • Otherwise, dp[i][j] = false

Code (TypeScript)

function isMatch(s: string, p: string): boolean {
    const m = s.length;
    const n = p.length;
    const dp: boolean[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));
    dp[0][0] = true;

    for (let j = 1; 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]; // '*' matches zero occurrences
                if (s[i - 1] === p[j - 2] || p[j - 2] === '.') {
                    dp[i][j] = dp[i][j] || dp[i - 1][j]; // '*' matches one or more occurrences
                }
            } else if (s[i - 1] === p[j - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

Complexity

• Time Complexity: O(mn), where m is the length of s and n is the length of p. We iterate through the dp table.
• Space Complexity: O(mn), due to the size of the dp table. This can be optimized to O(n) if we only keep track of the current and previous row of the dp table.