LeetCode第十题

Question

bobo老师，第十题的思路我和某个发布题解的作者一样(下面是题解的链接)，但是我还有一点歧义
![
就是我用红色框框圈起来的这个，我觉得当p中的下一个位置不是*时，与当前s的位置不匹配，应该查询p中的下一个位置与当前s的位置是否匹配，而不是直接返回false
http://img1.sycdn.imooc.com//szimg/5f32907509d8321a09430624.jpg)
https://leetcode-cn.com/problems/regular-expression-matching/solution/c-4ms-zhi-guan-fen-xi-by-fu-guang/

这是我的代码：
class Solution {
private:
bool doMatch(const string& s, int sIndex, const string& p, int pIndex) {
if (pIndex >= p.size()) return sIndex >= s.size();

    bool curElement = sIndex<s.size()&&(s[sIndex] == p[pIndex] || (p[pIndex] == '.'));
    if (pIndex + 1 < p.size() && p[pIndex+1] == '*') {
        return doMatch(s, sIndex, p, pIndex + 2) || curElement&&doMatch(s, sIndex + 1, p, pIndex);
    }
    else {
        if(curElement==true){
            return doMatch(s, sIndex + 1, p, pIndex + 1);
        }
        else{
            return doMatch(s,sIndex,p,pIndex+1);
        }
    }
}

public:
bool isMatch(string s, string p) {
return doMatch(s, 0, p, 0);
}
};

Answer 1

提问者 我是笨笨蛋 2020-08-13 20:36:56

这个样例

• 提问者 我是笨笨蛋 #1

  按照我对涵盖的理解，p涵盖s就意味着s是p的子集，根据这个样例ab显然是abc的子集

• liuyubobobo 回复 提问者 我是笨笨蛋 #2

  你对题目理解有问题，对正则表达式的理解也有问题。“.*c” 这个模式无法产生 “ab” 这个字符串。“.*c” 这个模式最后必须有 c 这个字母，“ab”不满足。我建议你简单学习一下正则表达式，挺有用的，绝对不亏。 网上有很多免费教程，比如这里：https://deerchao.cn/tutorials/regex/regex.htm（我随便搜的，不一定好。你可以搜索“正则表达式 教程”，找一找适合你的内容。）

Answer 2

liuyubobobo 2020-08-12 01:52:57

我还没有仔细看响应的逻辑，但我想先知道：

1）按照他的思路写出的代码是否是正确的？能否获得通过？

2）按照你的思路，改写代码，结果是否是正确的？是否能获得通过？

• 提问者 我是笨笨蛋 #1

  按照他的代码可以通过，我的不能。我在提问上附上了我的代码

• 提问者 我是笨笨蛋 #2

  题目说的是p要涵盖整个字符串s，既然是涵盖，我觉得p可以与s有不相同的字符，比如s=abc,p=cabc,依旧是p涵盖s，但是，我按照作者的代码对这个样例进行调试，返回的结果是false，难道是我对涵盖的理解是错误的吗？，请bobo老师指点

• liuyubobobo 回复 提问者 我是笨笨蛋 #3

  我测试了一下，你的代码是正确的？

点开查看后面1条评论