10. Regular Expression Matching (Hard)

Pyodide

Editor (session: default) Run

# Type here

Output Clear

Run

Editor (session: default) Run

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] == 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]

# --- Example Usage Code ---

sol = Solution()
print("--- Regular Expression Matching Examples ---")
# 

# Test Case 1: Simple mismatch
s1 = "aa"
p1 = "a"
result1 = sol.isMatch(s1, p1)
print(f"Input: s='{s1}', p='{p1}'")
print(f"Output: {result1} (Expected: False)")

# Test Case 2: Simple * match (one or more 'a')
s2 = "aa"
p2 = "a*"
result2 = sol.isMatch(s2, p2)
print(f"Input: s='{s2}', p='{p2}'")
print(f"Output: {result2} (Expected: True)")

# Test Case 3: Zero * match (zero 'a')
s3 = "ab"
p3 = ".*"
result3 = sol.isMatch(s3, p3)
print(f"Input: s='{s3}', p='{p3}'")
print(f"Output: {result3} (Expected: True)")

# Test Case 4: Multiple characters and *
s4 = "aab"
p4 = "c*a*b"
result4 = sol.isMatch(s4, p4)
print(f"Input: s='{s4}', p='{p4}'")
print(f"Output: {result4} (Expected: True) (c* matches zero c's, a* matches two a's)")

# Test Case 5: Complex match with '.' and '*'
s5 = "mississippi"
p5 = "mis*is*p*."
result5 = sol.isMatch(s5, p5)
print(f"Input: s='{s5}', p='{p5}'")
print(f"Output: {result5} (Expected: False)")

# Test Case 6: Edge Case (Pattern starts with '.*')
s6 = "abcd"
p6 = ".*d"
result6 = sol.isMatch(s6, p6)
print(f"Input: s='{s6}', p='{p6}'")
print(f"Output: {result6} (Expected: True)")

Output Clear

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

        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]

Function Description

Source code in python/_10.py

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] == 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]

isMatch(s, p)

Source code in python/_10.py

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] == 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

The problem asks you to implement a regular expression matching algorithm that supports two special characters: . (dot) and * (asterisk). The dot . matches any single character. The asterisk * matches zero or more occurrences of the preceding element. The matching must cover the entire input string \(s\) (not partial). You are given an input string \(s\) and a pattern \(p\). This problem is classified as Hard due to the complex state management required by the * operator.

The two main approaches to solving this problem are Recursion with Memoization (Top-Down Dynamic Programming) and Tabulation (Bottom-Up Dynamic Programming). The recursive approach checks if the current character in \(s\) matches the current element in \(p\). If the next element in \(p\) is *, this introduces two possibilities: either the * matches zero occurrences of the preceding element (so we move past both the element and * in \(p\)), or it matches one or more occurrences (so we stay at the * and move to the next character in \(s\)). Memoization is crucial to avoid re-calculating the same subproblems, which would otherwise lead to exponential time complexity.

The preferred \(O(m \times n)\) solution is the Bottom-Up Dynamic Programming approach, where \(m\) is the length of \(s\) and \(n\) is the length of \(p\). A 2D boolean array, \(DP[i][j]\), is used to store whether the substring \(s[0...i-1]\) matches the pattern \(p[0...j-1]\). The base cases involve empty strings. The recursive relations are built upon checking the current character match and the two conditions for the * operator. The final answer is found at \(DP[m][n]\). This approach systematically builds the solution from the smallest subproblems.