二哥曾说，心胸开阔一点，别斤斤计较，以前很喜欢的一个博主，书的写不错，但心胸是真的狭隘，还是二哥老乡，以前拿他做偶像，现在看来，有些人真的是徒有其名。不然好好刷 LeetCode 吧，这里没有烦恼。

题意

给你一个输入字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

难度

困难

示例

示例 1:

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

示例 2:

输入: s = "aa" p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3：

输入: s = "cb" p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

分析

其实我们很早就做过一到正则表达式的题：010.正则式匹配，大家还有印象吗？

当时是 . 和 *，现在是 ? 和 *。

10 中的 * 用来匹配零个或多个前面的那一个字符。

44 中的 * 用来匹配任意字符串，包括空字符串。

符号相同，但寓意上有所不同。

10 中的 . 可以匹配任意单个字符，而 44 中的 ? 也可以匹配任意单个字符。

符号不同，但寓意上完全相同。

10 题我们用了动态规划，这道题仍然可以用动态规划来解。

• 普通字符：需要和 s 中同一位置的字符完全匹配
• '?'：能够匹配 s 中同一位置的任意字符
• '*'：能够匹配任意字符串

前面两种情况都比较简单，因为只需要拿 p 中的同位置字符和 s 中的同位置字符进行比较即可。只要 p[i] == s[i] 或者 p[i] == '?'，那么就是匹配的。

但是 * 就比较复杂了，因为 * 可以匹配任意字符串，包括空字符串。所以我们需要考虑 * 匹配 0 个字符、1 个字符、2 个字符、...、n 个字符的情况。

假设在模式 p 中某个位置 p[j] 是 *，此时我们需要考虑多种匹配可能性：

• * 匹配 0 个字符：即 p[j] 和 s[i] 的当前字符没有匹配上，* 作为空字符