Wildcard Matching
Difficulty: Hard
这道题其实非常类似于Regular Expression Matching，而且似乎更简单一些。
同样，构造一个$(m+1)\times (n+1)$的矩阵d，d[i][j]表示p[:i]与s[:j]匹配。
可以用以下方式按行构造d.
首先d[0][0]为true，表示两个串的开头(^)匹配。
如果d[i-1][j-1]为true，可以分以下几种情况讨论
- Case 1: p[i-1]为”*“，那么这个星号可以与之后的每一个字符匹配，同时也有可能一个都不匹配，因此将第i行j-1位及之后均设为true.
- Case 2: p[i-1]为普通字符或”?”，那么如果其与s[j-1]匹配，就将d[i][j]设为true.
最后只需要判断d[m][n]是否为true即可。复杂度$\Theta(mn)$.
按照这道题的思路，其实可以优化一下Regular Expression Matching的解法，把这道题的复杂度也降到$\Theta(mn)$.