52 正则表达式匹配

题目描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。

解题思路

核心思想：动态规划。

状态定义：dp[i][j]表示s的前i个字符能否匹配p的前j个字符。

状态转移：

1. 如果p[j-1]是普通字符或'.'：dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1]
2. 如果p[j-1]是'*'：
   • 不使用'*'：dp[i][j] = dp[i][j-2]
   • 使用'*'：dp[i][j] = dp[i-1][j] && s[i-1]与p[j-2]匹配

时间复杂度：O(mn) 空间复杂度：O(mn)

Python 实现

def match(s, pattern):
    """
    正则表达式匹配

    Args:
        s: 字符串
        pattern: 正则表达式

    Returns:
        bool: 是否匹配
    """
    m, n = len(s), len(pattern)
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    # 空字符串匹配空模式
    dp[0][0] = True

    # 处理模式中的'a*'这样的组合
    for j in range(2, n + 1):
        if pattern[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if pattern[j - 1] == '*':
                # 不使用'*'
                dp[i][j] = dp[i][j - 2]
                # 使用'*'
                if pattern[j - 2] == s[i - 1] or pattern[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            else:
                # 普通字符或'.'
                if pattern[j - 1] == s[i - 1] or pattern[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]


# 测试代码
if __name__ == "__main__":
    test_cases = [
        ("aaa", "a.a"),
        ("aaa", "ab*ac*a"),
        ("aaa", "aa.a"),
        ("aaa", "ab*a"),
        ("", ".*"),
    ]

    for s, pattern in test_cases:
        result = match(s, pattern)
        print(f"'{s}' 匹配 '{pattern}': {result}")

# 输出:
# 'aaa' 匹配 'a.a': True
# 'aaa' 匹配 'ab*ac*a': True
# 'aaa' 匹配 'aa.a': True
# 'aaa' 匹配 'ab*a': False
# '' 匹配 '.*': True

图解

示例: s="aaa", pattern="a.a"

dp表:
      ''  'a'  '.'  'a'
''    T   F    F    F
'a'   F   T    F    F
'aa'  F   F    F    F
'aaa' F   F    F    T

匹配过程:
- 'a' 匹配 'a'
- 'a' 匹配 '.'
- 'a' 匹配 'a'

最终: dp[3][3] = True