LeetCode:10.正则表达式匹配；44. 通配符匹配；

最新推荐文章于 2024-03-24 11:46:53 发布

Raven_csdn

最新推荐文章于 2024-03-24 11:46:53 发布

阅读量447

点赞数 2

分类专栏： LeetCode 文章标签： LeetCode 正则表达式匹配通配符匹配

本文链接：https://blog.csdn.net/Raven_csdn/article/details/90316706

版权

LeetCode 专栏收录该内容

15 篇文章

订阅专栏

这篇博客深入探讨了LeetCode中的两道经典问题——10.正则表达式匹配和44.通配符匹配。通过递归算法详细解释了解题思路，帮助读者理解如何实现这两种匹配方式。

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

10.正则表达式的匹配
在这里插入图片描述

注释程序去解答题目，递归

class Solution {
public:
    bool isMatch(string s, string p) {
        return matchCore((char*)s.c_str(),(char*)p.c_str());
    }
    bool matchCore(char *str,char * pat){
        if(*str=='\0' && *pat=='\0')  //str同时为空
            return true;
        if(*str!='\0' && *pat=='\0')
            return false;
        if(*(pat+1)=='*'){//如果后面是*的话怎么办
            if(*pat==*str || (*pat=='.' && *str!='\0')){
                //     abc---->a*bc 星号隔过去     aaaabc---->a*bc利用星号的下一次重复   a---->a*a  将本次隔过去
                return matchCore(str+1,pat+2) || matchCore(str+1,pat) || matchCore(str,pat+2);
            }else{
                //     abc---->d*bc  将本次隔过去
                return matchCore(str,pat+2);
            }
        }
        //这个没有疑问直接往后移动就可以了 abc-->abc   abc--->.bc
        if(*str==*pat || (*pat=='.' && *str!='\0'))
            return matchCore(str+1,pat+1);
        return false;
    }
};

44. 通配符匹配；
在这里插入图片描述

class Solution {
    //动态规划
    //m[i][j]表示s(0 ~ i-1)和 p(0 ~ j-1)是否匹配
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> m(s.size()+1,vector<bool>(p.size()+1));
        
        m[0][0] = true; //两个字符串都为空是肯定匹配
        for(int i = 0; i <= s.length(); i++) {
            for(int j = 1; j <= p.length(); j++) {
                if(p[j-1] == '*') {
                    //m[i][j-1] 即当前'*'匹配一个空字符
                    //m[i-1][j] 即当前'*'匹配一个字符s.charAt(i-1)
                    //这里之所以不是m[i-1][j-1]是因为当前'*'可能在前面一匹配了若干个字符
                    //         abc,ab[*]
                    m[i][j] = m[i][j-1] || (i > 0 && m[i-1][j]);
                } else {
                    //前面的m(0~i-2)和p(0~j-2)能匹配且当前字符能匹配
                    //比如abc,abd
                    m[i][j] = i > 0 && m[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
                }
            }
        }
        return m[s.length()][p.length()];
    }
    
};