正则表达式匹配

正则表达式匹配_牛客题霸_牛客网

问题简述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。
1.模式中的字符'.'表示任意一个字符
2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

思路：动态规划

• 定义 dp(i, j) 表示 s[:i] 与 t[:j] 是否匹配；

• 难点是要把所有情况考虑全面，主要是初始化，和 p[j - 1] == '*' 的情况；

Python 递归写法

class Solution:
    def match(self , s: str, t: str) -> bool:
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == 0 and j == 0: return True
            if j == 0: return False
            if i == 0: # s='', t='a*b*' 的情况
                return j > 1 and t[j - 1] == '*' and dp(0, j - 2)
            
            # s='abc', t='abc' 或 'ab.'
            r1 = (s[i - 1] == t[j - 1] or t[j - 1] == '.') and dp(i - 1, j - 1)
            # s='abc', t='abcd*' 的情况，* 匹配了 0 个字符，所以下一步需要跳过 *，即 dp(i, j-2)
            r2 = j > 1 and t[j - 1] == '*' and dp(i, j - 2)
            # s='abc', t='abc*' 或 'ab.*' 的情况，* 匹配了至少 1 和字符，下一步需要继续尝试匹配 *，所以是 dp(i-1, j)
            r3 = j > 1 and t[j - 1] == '*' and (s[i - 1] == t[j - 2] or t[j - 2] == '.') and dp(i - 1, j)
            
            return r1 or r2 or r3
        
        # 本题保证了提供的 t 是合法的，所以其实可以去掉 j>1 的判断
        return dp(len(s), len(t))

Python 迭代写法

class Solution:
    def match(self , s: str, t: str) -> bool:
        
        m, n = len(s), len(t)
        # dp[i][j] 表示的是 s[:i] 和 t[:j] 是否匹配，所以需要初始化为 m+1 和 n+1
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m + 1):  # 遍历范围是 0 ~ m+1
            for j in range(n + 1):  # 遍历范围是 0 ~ n+1
                if i == 0 and j == 0: dp[i][j] = True
                elif j == 0: dp[i][j] = False
                elif i == 0: # s='', t='a*b*' 的情况
                    dp[i][j] =  j > 1 and t[j - 1] == '*' and dp[0][j - 2]
                else:
                    # s='abc', t='abc' 或 'ab.'
                    r1 = (s[i - 1] == t[j - 1] or t[j - 1] == '.') and dp[i - 1][j - 1]
                    # s='abc', t='abcd*' 的情况，* 匹配了 0 个字符，所以下一步需要跳过 *，即 dp(i, j-2)
                    r2 = j > 1 and t[j - 1] == '*' and dp[i][j - 2]
                    # s='abc', t='abc*' 或 'ab.*' 的情况，* 匹配了至少 1 和字符，下一步需要继续尝试匹配 *，所以是 dp(i-1, j)
                    r3 = j > 1 and t[j - 1] == '*' and (s[i - 1] == t[j - 2] or t[j - 2] == '.') and dp[i - 1][j]

                    dp[i][j] = r1 or r2 or r3
        
        # 本题保证了提供的 t 是合法的，所以其实可以去掉 j>1 的判断
        return dp[-1][-1]