题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。
'.' 匹配任意单个字符
'' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

题解：

回溯法

设输入文本串s,模式串为p,当前s的匹配位置为sIndex，p的位置为pIndex。
函数doMatch(s,sIndex,p,pIndex)表示s串从sIndex开始的子串与模式串p中从pIndex开始的子串是否匹配（均包括Index位置）。

  1. 当前位置的匹配情况为:

    bool currentMatch = s[sIndex] == p[pIndex] || p[pIndex] == '.';

  2. 除了当前位置的情况，还应该考虑到p中下一个位置可能是'*'：

（1）如果当前位置是不匹配，则要想结果匹配，只能使x匹配0个x字符。即使当前位置匹配，仍有可能实际要跳过x才能使得最终的结果匹配，例如：s = abbc, p = abbbc,b*必须一个都不匹配才能使得p中后面两个bb与s中的bb匹配。因此，只要下一个位置是,就要考察跳过x,此时sIndex不变，令pIndex += 2跳过即可:

doMatch(s, sIndex, p, pIndex + 2)

（2）如果当前位置匹配，则直接令sIndex+1考察sIndex的下一个位置（是否匹配x*）:

doMatch(s, sIndex + 1, p, pIndex)

（3）当p中下一个位置不是*时：
当前位置匹配，则继续考察下一个位置：

doMatch(s, sIndex + 1, p, pIndex + 1);

当前位置不匹配,则以这个位置开始的字串也不会匹配，返回false。

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

    static bool doMatch(const string& s, int sIndex, const string& p, int pIndex)
    {
        int sSize = s.size();
        int pSize = p.size();
        if(pIndex>=pSize)
            return sIndex>=sSize;

        //判定当前字符是否合法
        bool currentMatch = sIndex<sSize && (s[sIndex]==p[pIndex] || p[pIndex]=='.');

        //如果模式的下一个字符是*，需要单独考虑
        if((pIndex+1)<pSize && p[pIndex+1]=='*')
        {
            //一种情况是直接跳过这a*模式（他们的个数为0）
            //一种情况是当前字符匹配，那么将源字符串的下标加1，模式的下标不变，进行递归
            return doMatch(s,sIndex,p,pIndex+2)||(currentMatch && doMatch(s,sIndex+1,p,pIndex));
        }
        else
        {
            //如果模式的下一个字符不是*，那么就直接递归进行下一个字符的比较
            return currentMatch && doMatch(s,sIndex+1,p,pIndex+1);
        }
    }
};