C++，dp，递归，字符串匹配。
像这种题，最容易忘记，索性思路写的详细一点。
大体思路：使用从前往后“消除”的思路，使用双指针，对于指针之前的可以不管，只判断当前位置和以后的字符串的匹配情况，然后使用相同的策略进行递归匹配。
详细匹配步骤：
- 如果s和p指针都指向\0，则说明已经全部匹配成功了；
- 如果s和p指针指向的字符相等或者是p指向的是
.，说明当前字符匹配成功：- 如果p的下一个字符是
*，说明p可以重复前一个字符0次-n次：- 如果是需要重复前一个字符0次，则说明消除上一个字符，则下次匹配应该从
*的下一个字符开始，也就是改变递归参数：return match(s, p + 2); - 如果是需要重复前一个字符1-n次，则下次匹配就应该直接从
p指针指向字符开始就好，也就是递归return match(s + 1, p); - 所以应该合并上述两种情况，也就是
return match(s + 1, p) || match(s, p + 2);
- 如果是需要重复前一个字符0次，则说明消除上一个字符，则下次匹配应该从
- 如果不是
*，直接进行下一层匹配就好return match(s + 1, p + 1);
- 如果p的下一个字符是
- 如果当前字符没有匹配成功：
- 如果
p的下一个字符是*，说明可以重复前一个字符0次，也就是把当前字符不匹配给消去，然后继续下一层匹配return match(s, p + 2); - 如果没有
*，说明这里已经匹配失败了，返回false就好
- 如果
代码如下：
class Solution {
public:
bool isMatch(sing s, sing p) {
return match(s.data(), p.data());
}
bool match(char *s, char *p) {
if (*p == 0) return *s == 0;
else if (*s == *p || (*s != 0 && *p == '.')) {
if (*(p + 1) == '*')
return match(s, p + 2) || match(s + 1, p);
else return match(s + 1, p + 1);
} else if (*(p + 1) == '*')
return match(s, p + 2);
else return false;
}
};
