leetcode10. Regular Expression Matching

最新推荐文章于 2024-02-23 10:40:54 发布

Coding_Reading

最新推荐文章于 2024-02-23 10:40:54 发布

阅读量345

点赞数

分类专栏： C++ 字符串

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/77839838

版权

C++ 同时被 2 个专栏收录

17 篇文章

订阅专栏

字符串

8 篇文章

订阅专栏

本文介绍了一种解决正则表达式匹配问题的算法实现，采用动态规划的方法，通过二维数组记录子串间的匹配状态。文章详细解释了如何处理特殊字符如'*'的情况，并提供了完整的C++代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

难度：hard

题目：

这里写图片描述

AC解：

class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.length();
        int plen = p.length();

        if (slen == 0 && plen == 0)
            return true;

        vector<vector<bool>> dp(slen + 1, vector<bool>(plen + 1, false));
        //初始化数组
        dp[0][0] = true;
        //p为a*a*...此种情况
        for (int i = 2; i <= plen; i += 2) {
            if (dp[0][i - 2] && p[i - 1] == '*')
                dp[0][i] = true;
        }

        for (int i = 1; i < slen + 1; i++)
            for (int j = 1; j < plen + 1; j++) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                if (p[j - 1] == '*') {
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.')
                        //分别为重复0, 1,多次
                        dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                    else
                        dp[i][j] = dp[i][j - 2];  //s[i - 1] 和 p[j - 2]不相等，重复0次
                }
            }
        return dp[slen][plen];
    }
};