LeetCode Problem #10: Regular Expression Matching - Explanation and Solutions in Python and JavaScript

Introduction

The Regular Expression Matching problem is a challenging problem that tests your understanding of dynamic programming and string manipulation. It is frequently asked in coding interviews to assess your problem-solving skills. In this post, we'll break down the problem, explain the optimal approach, and provide solutions in both Python and JavaScript.

Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

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

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

Example:

Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 2 times. Therefore, it matches "aab".
    

Approach

The problem can be solved efficiently using **dynamic programming**. Here's the step-by-step approach:

1. Create a 2D DP table where dp[i][j] represents whether the first i characters of s match the first j characters of p.
2. Handle base cases:
   • Empty string and empty pattern match (dp[0][0] = true).
   • Empty string and non-empty pattern can match if the pattern contains '*'.
3. Fill the DP table based on the following rules:
   • If the current characters match or the pattern has '.', check the previous state (dp[i-1][j-1]).
   • If the pattern has '*', consider two cases:
     • Zero occurrences of the preceding element (dp[i][j-2]).
     • One or more occurrences of the preceding element (dp[i-1][j]).

Solution in Python

def isMatch(s, p):
    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] == s[i - 1] or p[j - 1] == '.':
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                dp[i][j] = dp[i][j - 2]
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]

    return dp[m][n]
        

Explanation: We use a 2D DP table to store intermediate results. We handle base cases and fill the table based on the rules for matching characters, '.', and '*'.

Solution in JavaScript

function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({ length: m + 1 }, () => 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] === s[i - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2];
                if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }

    return dp[m][n];
}
        

Explanation: Similar to the Python solution, we use a 2D DP table to store intermediate results. We handle base cases and fill the table based on the rules for matching characters, '.', and '*'.

Time and Space Complexity

Time Complexity: O(m * n) - We fill a 2D DP table of size (m+1) x (n+1).
Space Complexity: O(m * n) - We use a 2D DP table of size (m+1) x (n+1).

Edge Cases

• Empty string and empty pattern.
• Empty string and pattern with '*'.
• Pattern with multiple '*' characters.
• Strings with repeating characters and patterns with '.' and '*'.

Conclusion

The Regular Expression Matching problem is a great way to practice dynamic programming and string manipulation. By understanding this approach, you can solve similar problems like Wildcard Matching or Longest Common Subsequence. Try solving it on your own and explore related problems on LeetCode!