题目描述
解题思路
- 本题的主流解法包括两种，主要是递归回溯与动态规划，鉴于动态规划不易理解，本文采用递归回溯的方法进行讲解，步骤如下：
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为空我们跳转到后面的第三步。
- s的第一个字符和p的第一个字符相等，或者p的第一个字符为 "."，都说明成功匹配到了。
- 判断字符串p的长度，此时存在两种情况，一种是小于2，一种是大于等于2，如果小于2，我们就没必要判断当前字符p的第二个字符是不是*号了，直接将s去掉首元素和p去掉首元素，投入到递归函数中去继续判断，如果大于等于2的情况，则是有必要继续判断的，我们要判断p字符的第二个字符是不是*号的，如果第二个是*号则存在两种情况，一个是这个*号代表前面的字符出现了0次，另一种情况是前面的字符出现了多次，此时我们就要分情况讨论了，如果代表的是0次，则将s不变和p去掉前两个字符，投入递归函数，如果代表的是多次，我们首先当作一次，把s去掉首元素，p不变继续递归。
- 如果字符串p的长度小于2，由于前面的条件限制使得首元素是相同的，我们只用将s和p分别去掉首元素，继续投入递归，由结束条件来帮助我们继续判断。
- 如果字符串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; } } };
总结（本题给我们的启示思路）
- 学会通过递归回溯解决多边界条件问题
- 本题的难点在于*这种情况的考虑，刚开始不会也是正常，千万不要焦躁，不要放弃，仔细想想总会解出来的。
