10. Regular Expression Matching

• categories: Code, Interview Question, leetcode, Hard
• source: https://leetcode.com/problems/regular-expression-matching
• topics: String Manipulation, Dynamic Programming

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

Recursion

class Solution(object):
    def isMatch(self, text: str, pattern: str) -> bool:
        if not pattern:
            return not text
 
        first_match = bool(text) and pattern[0] in {text[0], "."}
 
        if len(pattern) >= 2 and pattern[1] == "*":
            return (
                self.isMatch(text, pattern[2:])
                or first_match
                and self.isMatch(text[1:], pattern)
            )
        else:
            return first_match and self.isMatch(text[1:], pattern[1:])

Dynamic Programming

class Solution(object):
    def isMatch(self, text: str, pattern: str) -> bool:
        memo = {}
 
        def dp(i, j):
            key = (i, j)
            if key in memo:
                return memo[key] 
 
            if j == len(pattern):
                return i == len(text)
 
            first_match = i < len(text) and pattern[j] in {text[i], "."}
 
            if j < (len(pattern) - 1) and pattern[j+1] == "*":
                memo[key] = dp(i, j + 2) or first_match and dp(i+1, j)
            else:
                memo[key] = first_match and dp(i+1, j+1)
            
            return memo[key]
 
        return dp(0,0)