c++ - Leet Code 正则表达式匹配问题

Question

https://leetcode.com/problems/regular-expression-matching
我正在做这个练习题(cpp)，虽然评论中有更快的解决方案，但我想了解为什么我的代码不起作用。这失败了 s = "mississippi"和 p = "mis*is*p*." .跟踪代码，我认为它会正确删除前两个字母，然后当看到 s* 时，它会遍历字符串中的 s(其中两个)，然后删除两者中的 i，删除所有 s(再次2) 然后删除所有的 p(没有，因为它与第一个字符串中的 i 进行比较，所以它不应该修改该字符串)。最后，'.'将与第一个 p 匹配并删除两者。所以最后的字符串应该是“pi”，当长度与零比较时返回false。

class Solution {
public:
    bool isMatch(string s, string p) {
        
        while (s.length() > 0){
            if (p.length() == 0){
                return false;
            }else if (p.length() == 1){
                return p.compare(s) == 0 || p.at(0) == '.';
            }else{
                if (p.at(1) == '*'){
                    char c = p.at(0);
                    p = p.substr(2);
                    if (c == '.'){
                        return true;
                    }
                    int spot = 0;
                    while(spot < s.length() && s.at(spot) == c){
                        spot++;
                    }
                    if (spot != 0){
                    s = s.substr(spot);
                    }
                }else{
                    if (s.at(0) != p.at(0) && p.at(0) != '.'){
                        return false;
                    }
                    s = s.substr(1);
                    p = p.substr(1);
                }
            }
        }
        return s.length() == 0;
    }
};

Answer 1

你的逻辑在这里有问题

return p.compare(s) == 0 || p.at(0) == '.';

那应该是

return p.compare(s) == 0 || (s.length() == 1 && p.at(0) == '.');

我花了五分钟才找到，两分钟查看代码却没有发现问题，然后三分钟使用调试器来追踪逻辑错误。您真的应该学习使用调试器，这比询问 SO 高效得多。
一些提示 here .