题目描述

解题思路

• 本题的主流解法包括两种，主要是递归回溯与动态规划，鉴于动态规划不易理解，本文采用递归回溯的方法进行讲解，步骤如下：

1. 判断p字符串是否为空，如果为空则继续判断字符串s是否为空

• 我们首先要准确理解字符s和字符p的含义，字符s代表的是待匹配的字符串，而字符串p则代表的是我们的匹配模式
• 如果匹配模式为空，我们要看待匹配的字符s是否为空，如果两者皆为空，说明空匹配空，结果返回true,如果p为空，但是s不为空，说明让空去匹配非空，肯定false,这是我们递归的出口。

if (p.length === 0) {
    if (s.length === 0) {
        return true;
    } else {
        return false;
    }
}

2. 判断在字符串s非空的情况下，第一个字符是否能够成功匹配

• 为什么要在字符串s非空的情况下，去进行匹配？

答：因为字符串s如果为空，去匹配第一个字符是没有意义的，如果字符s为空，且能够走到这里，说明字符串p不为空，要不然也不能走到第二步就返回了，如果字符s为空我们跳转到后面的第三步。

1. s的第一个字符和p的第一个字符相等，或者p的第一个字符为 "."，都说明成功匹配到了。
2. 判断字符串p的长度，此时存在两种情况，一种是小于2，一种是大于等于2，如果小于2，我们就没必要判断当前字符p的第二个字符是不是*号了，直接将s去掉首元素和p去掉首元素，投入到递归函数中去继续判断，如果大于等于2的情况，则是有必要继续判断的，我们要判断p字符的第二个字符是不是*号的，如果第二个是*号则存在两种情况，一个是这个*号代表前面的字符出现了0次，另一种情况是前面的字符出现了多次，此时我们就要分情况讨论了，如果代表的是0次，则将s不变和p去掉前两个字符，投入递归函数，如果代表的是多次，我们首先当作一次，把s去掉首元素，p不变继续递归。
3. 如果字符串p的长度小于2，由于前面的条件限制使得首元素是相同的，我们只用将s和p分别去掉首元素，继续投入递归，由结束条件来帮助我们继续判断。
4. 如果字符串s为空，或者第一个字符不匹配，我们首先判断p的长度，如果p的长度是小于2的，当前元素不同，后面又没有*了，所以直接返回false,如果p的长度是大于等于2的，继续判断p的第二个元素是不是*，如果是，则将s不变，p去掉两个首元素继续递归判断，如果第二个元素不是*，直接返回false.

解题代码

var isMatch = function (s, p) {
    // 判断模式p是否为空，如果为空，则判断s是否为空
    if (p.length === 0) {
        if (s.length === 0) {
            return true;
        } else {
            return false;
        }
    }
    // 判断第一个字符是否匹配
    if (s.length !== 0 && (s[0] === p[0] || p[0] === '.')) {
        // 走到这里说明，第一个字符是匹配的
        if (p.length >= 2) {
            // 判断第二个字符是不是 *
            if (p[1] === '*') {
                return isMatch(s, p.slice(2)) || isMatch(s.slice(1), p)
            } else {
                return isMatch(s.slice(1), p.slice(1));
            }
        } else {
            return isMatch(s.slice(1), p.slice(1));
        }
    } else {
        if (p.length >= 2) {
            if (p[1] === '*') {
                return isMatch(s, p.slice(2));
            } else {
                return false;
            }
        } else {
            return false;
        }
        
    }
};

总结（本题给我们的启示思路）

• 学会通过递归回溯解决多边界条件问题
• 本题的难点在于*这种情况的考虑，刚开始不会也是正常，千万不要焦躁，不要放弃，仔细想想总会解出来的。