题目描述（困难难度）

字符串匹配，? 匹配单个任意字符，* 匹配任意长度字符串，包括空串。和第 10 题有些类似。

解法一 动态规划

直接按照之前第 10 题，修改一下就可以了。

同样是用 dp[i][j] 表示所有的情况，然后一层一层的根据递推关系求出来。

时间复杂度：text 长度是 T，pattern 长度是 P，那么就是 O（TP）。

空间复杂度：O（TP）。

时间复杂度：text 长度是 T，pattern 长度是 P，那么就是 O（TP）。

空间复杂度：O（P）。

解法二 迭代

参考这里，也比较好理解，利用两个指针进行遍历。

时间复杂度：如果 str 长度是 T，pattern 长度是 P，虽然只有一个 while 循环，但是 s 并不是每次都加 1，所以最坏的时候时间复杂度会达到 O（TP），例如 str = “bbbbbbbbbb”，pattern = “*bbbb”。每次 pattern 到最后时，又会重新开始到开头。

空间复杂度：O（1）。

递归

如果非要用递归的话，可以按照动态规划那个思路，先压栈，然后出栈过程其实就是动态规划那样了。所以其实不如直接动态规划。

总

动态规划的应用，理清递推的公式就可以。另外迭代的方法，也让人眼前一亮。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^