原题
判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个串完全匹配才算匹配成功。
函数接口如下:
bool isMatch(const char *s, const char *p)
一些例子：
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
解题思路
- 动态规划，内存需要优化，滚动数组, 10000 * 10000 转化成 2 * 10000
- 状态cache[i][j]表示S的前i和T的前j是否match
- 状态转移
- 如果PD[i-1][j]==true或者PD[i][j-1]==true，并且s[i]=='*'或者p[j]=='*'时PD[i][j]==true；
- 如果PD[i-1][j-1]==true时，s[i]与p[j]匹配，则PD[i][j]==true。
- 换句话说，一个格子的True或者False只与左侧，左上和上方的格子有关，如下图
Screenshot at Jun 05 04-37-09.png
完整代码
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(p) - p.count('*') > len(s): #avoid TLE(Time Limited Exceeded)
return False
cache = [[False for i in range(len(s) + 1)] for j in range(2)]
cache[0][0] = True
for j in range(1, len(p) + 1):
cache[j % 2][0] = cache[(j - 1) % 2][0] and p[j - 1] == "*"
for i in range(1, len(s) + 1):
cache[j % 2][i] = False
if s[i - 1] == p[j - 1] or s[i - 1] == "?" or p[j - 1] == "?":
cache[j % 2][i] = cache[(j - 1) % 2][i - 1]
if s[i - 1] == "*" or p[j - 1] == "*":
cache[j % 2][i] = cache[(j - 1) % 2][i] or cache[j % 2][i - 1]
return cache[len(p) % 2][len(s)]
