题解 | 正则表达式匹配

1、解题思路

1. 动态规划：定义 dp[i][j] 表示 str 的前 i 个字符和 pattern 的前 j 个字符是否匹配。状态转移： 如果 pattern[j-1] == '*' ： 匹配0次：dp[i][j] = dp[i][j-2]匹配1次或多次：(str[i-1] == pattern[j-2] || pattern[j-2] == '.') && dp[i-1][j]否则： (str[i-1] == pattern[j-1] || pattern[j-1] == '.') && dp[i-1][j-1]边界条件： dp[0][0] = true（空字符串和空模式匹配）dp[0][j]（空字符串和模式 pattern[0..j-1] 匹配的条件）
2. 递归方法：递归检查每个字符的匹配情况，处理 '*' 的特殊匹配规则。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        int m = str.size(), n = pattern.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (pattern[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (pattern[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || ((str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.') && dp[i - 1][j]);
                } else {
                    dp[i][j] = (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.') && dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        int m = str.length(), n = pattern.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (pattern.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pattern.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2] || 
                               ((str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.') && dp[i - 1][j]);
                } else {
                    dp[i][j] = (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
class Solution:
    def match(self , str: str, pattern: str) -> bool:
        # write code here
        m, n = len(str), len(pattern)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, 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] or \
                               ((str[i - 1] == pattern[j - 2] or pattern[j - 2] == '.') and dp[i - 1][j])
                else:
                    dp[i][j] = (str[i - 1] == pattern[j - 1] or pattern[j - 1] == '.') and dp[i - 1][j - 1]
        return dp[m][n]

3、复杂度分析

1. 初始条件： dp[0][0] = true（空字符串和空模式匹配）。dp[0][j]（空字符串和模式的匹配条件）。
2. 状态转移： '*' 匹配0次或多次时的逻辑处理。普通字符或 '.' 的匹配逻辑。
3. 复杂度分析： 时间复杂度：O(m*n)，填充 m×n 的 dp 表。空间复杂度：O(m*n)，存储 dp 表。

进阶思考

• 如果需要优化空间复杂度，可以使用滚动数组将空间复杂度降至 O(n)。
• 如果需要处理更复杂的正则表达式（如 '+'、'?' 等），可以扩展状态转移逻辑。