LeetCode #10 - Regular Expression Matching

Hello, coding enthusiasts! Today, we’re going to unravel another challenging problem from LeetCode: “Regular Expression Matching”.

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 1:

Input:s = "aa", p = "a"
Output:false
Explanation: "a" does not match the entire string "aa".

Example 2:

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

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Analysis

Our task is to implement a regular expression matcher. We need to handle cases such as matching any character, matching zero or more of the preceding element, and matching the entire string.

Approach

The most efficient approach to solve this problem is to use Dynamic Programming.

Understand the problem: The problem is to implement regular expression matching with support for '.' and ''. Here '.' Matches any single character, and '' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
Initialize the DP array: We create a 2D boolean DP array. The size of the array is (length of string + 1) x (length of pattern + 1). The extra row and column are for the case when the string or pattern is empty. If both strings are empty, then it’s a match, thus, dp[0][0] = true.
Handle the base cases: For non-empty strings, there are three cases to consider: if the characters are the same, if the pattern character is '.', or if the pattern character is ''. The DP array is filled accordingly. For example, if the pattern character is '', dp[0][i] = dp[0][i - 2] for i >= 2.
Fill the DP array: For the remaining characters, we iterate through the string and pattern character by character. If the current characters in the string and pattern are the same or the pattern character is '.', we set dp[i][j] = dp[i - 1][j - 1]. If the pattern character is '*', we have two sub-cases to consider. If the preceding character in the pattern is the same as the current character in the string or it is '.', we set dp[i][j] = dp[i][j - 2] or dp[i - 1][j]. Otherwise, we set dp[i][j] = dp[i][j - 2].
Return the result: The result is stored in dp[rows][columns], which represents whether the whole string matches the whole pattern.

Time Complexity

The time complexity for this approach is O(m*n), where m is the length of the string and n is the length of the pattern. This is because we’re processing each character once.

Space Complexity

The space complexity is O(m*n), as we’re using a 2D DP array to store the results.

Code

Here’s the Python and JavaScript code for this approach:

Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        rows, columns = len(s), len(p)

        # DP array
        dp = [[False for _ in range(columns + 1)] for _ in range(rows + 1)]
        dp[0][0] = True  # Since empty string and empty pattern are a match

        # Deals with patterns containing '*'
        for i in range(2, columns + 1):
            if p[i - 1] == '*':
                dp[0][i] = dp[0][i - 2]

        # For remaining characters
        for i in range(1, rows + 1):
            for j in range(1, columns + 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]
                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]

        return dp[rows][columns]

JavaScript

var isMatch = function (s, p) {
 const rows = s.length;
 const columns = p.length;
 if (rows == 0 && columns == 0) {
  return true;
 }
 if (columns == 0) {
  return false;
 }
 const dp = Array.from({ length: s.length + 1 }, () => [false]);
 dp[0][0] = true;
 for (let i = 1; i < columns + 1; i++) {
  if (p[i - 1] === '*') {
   dp[0][i] = dp[0][i - 2];
  }
  else {
   dp[0][i] = false;
  };
 }
 for (let i = 1; i < rows + 1; i++) {
  for (let j = 1; j < columns + 1; j++) {
   if (p[j - 1] === '*') {
    if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
     dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
    } else {
     dp[i][j] = dp[i][j - 2];
    }
   } else if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
    dp[i][j] = dp[i - 1][j - 1];
   } else {
    dp[i][j] = false;
   }
  }
 }
 return dp[rows][columns];
};

Conclusion

In this post, we tackled the “Regular Expression Matching” problem from LeetCode using the Dynamic Programming approach. This solution has a time complexity of O(mn) and a space complexity of O(mn).

Happy coding 😄!

Learn More:

LeetCode #10 – Regular Expression Matching