【力扣】[热题HOT 100] 10.正则表达式匹配

  • 时间:
  • 浏览:
  • 来源:互联网

1.题目

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

链接:https://leetcode-cn.com/problems/regular-expression-matching/

 

2.思路解析

  • 这里采用递归的方式,效率还是比较低的
  • 先判断s是不是空,对于空的情况,然后判断s只要的个数只要是奇数就返回false
  • 要是偶数,那么就遍历2,4,6位置是不是*,不是的话就返回false
  • 用两个变量cs,cp记录两个字符,cpNext记录p的下一个字符
  • cpNext是* 不是*的话,就直接比较,不匹配就false,匹配就利用substr截断1号下标到结尾的字符
  • 如果cpNext是* 的情况,那么判断cs和cp相等的话,那么有可能是cs下一个字符和 * 的下一个字符匹配的话,就s不变,p截断下标2到结尾的字符,如果cs下一个字符和*下一个字符不匹配,那么就让p往后走一步,最后会返回false
  • 如果此时的cs和cp不相等,那么就让p往后走一步,此时的 *前面字符的个数就是0,然后判断下来的字符是不是匹配的

3.代码展示

class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.empty())
        {
            if(p.size() & 1) return false;
            int odd = 1;
            while(odd < p.size())
            {
                if(p[odd] != '*') return false;
                odd += 2;
            }
            return true;
        }
        if(p.length() == 0) return false;

        char cs = s[0], cp = p[0], cpNext = '\0';
        if(p.length() > 1) cpNext = p[1];
        if(cpNext != '*')
        {
            if(cs == cp || cp == '.')
                return isMatch(s.substr(1), p.substr(1));
            else 
                return false;
        }
        else
        {
            if(cs == cp || cp == '.')
                return isMatch(s.substr(1), p) || isMatch(s, p.substr(2));
            else
                return isMatch(s, p.substr(2));
        }
    }
};

本文链接http://www.dzjqx.cn/news/show-617117.html