Regular Expression Matching - Leetcode Solution

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).

Note:

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 *.

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

Example 2: Input: s = "aab", p = "cab" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, "cab" matches "aab".

Solution

To solve this problem, we can use a dynamic programming approach. We can create a two-dimensional boolean array dp, where dp[i][j] represents whether the substring of s from 0 to i-1 can be matched with the substring of p from 0 to j-1.

Here are the steps to fill out the dp array:

1. Initialize dp[0][0] as true since an empty string can match another empty string.
2. Fill in the first row dp[0][j] according to the pattern. If p[j-1] is '', then dp[0][j] is equal to dp[0][j-2] (because '''' means zero or more of the preceding element).
3. Fill in the first column dp[i][0] as false since a non-empty string cannot match an empty pattern.
4. For each dp[i][j], if s[i-1] == p[j-1] or p[j-1] == '.', we can match the characters. Therefore, dp[i][j] is equal to dp[i-1][j-1].
5. If p[j-1] == '', there are two cases to consider: a) if p[j-2] == s[i-1] or p[j-2] == '.', the '' can either match zero or more characters. Therefore, we need to check dp[i][j-2] (zero match) or dp[i-1][j] (one or more matches) b) if p[j-2] != s[i-1], the '*' can only match zero characters. Therefore, dp[i][j] is equal to dp[i][j-2]

Finally, we return dp[m][n], where m and n are the lengths of s and p respectively.

Here is the Python code for the solution:

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

    # Fill in the first row dp[0][j]
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]
    
    # Fill in the first column dp[i][0]
    # (Already initialized as False)
    
    # Fill in the rest of the dp array
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == p[j-1] or p[j-1] == '.':
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                if p[j-2] == s[i-1] or p[j-2] == '.':
                    dp[i][j] = dp[i][j-2] or dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-2]
    
    return dp[m][n]

Time Complexity: O(mn), where m and n are the lengths of s and p respectively. Space Complexity: O(mn), the size of the dp array.

1