Chen's Blog

10. Regular Expression Matching

 
  • 2023年 06月23日

Promble

Link: https://leetcode.com/problems/regular-expression-matching/description/

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

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

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

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

Approach 1

Recursion

Thought

  1. judge if not p: return not s. (this is the exit of the recursion.)
  2. first_match = bool(s) and p[0] in {s[0], ‘.’}. # in every recursion, we judge the first index in p and s.
  3. if len(p) >= 2 and p[1] == ‘*’
    1. return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
    2. else: return first_match and self.isMatch(s[1:], p[1:])

⚠️ occur the TLE error.

Code

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s
        first_match = bool(s) and p[0] in {s[0], '.'}

        if len(p) >= 2 and p[1] =='*':
            return (self.isMatch(s, p[2:])) or \
            first_match and self.isMatch(s[1:], p)

        else:
            return first_match and self.isMatch(s[1:],p[1:])

Approach 2

DP

Code

class Solution(object):
    def isMatch(self, text, pattern):
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(pattern):
                    ans = i == len(text)
                else:
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)

Approach 3

use lib.

Code

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        return re.fullmatch(p, s)
搜索