LintCode 192. 通配符匹配
题目描述
判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：
1、'?' 可以匹配任何单个字符；
2、'*' 可以匹配任意字符串（包括空字符串）
两个串完全匹配才算匹配成功。
1<=|s|, |p| <= 1000
s仅包含小写英文字母
p包含小写英文字母，？和 *
测试样例
输入:
"aa"
"a"
输出: false
输入:
"aa"
"aa"
输出: true
输入:
"aaa"
"aa"
输出: false
输入:
"aa"
"*"
输出: true
说明: '*' 可以替换任何字符串
输入:
"aa"
"a*"
输出: true
输入:
"ab"
"?*"
输出: true
说明: '?' -> 'a' '*' -> 'b'
输入:
"aab"
"c*a*b"
输出: false
解题思路
1、记忆化搜索
每次搜索判断s从i位置开始的后缀和p从j位置开始的后缀可否匹配，使用一个dict来存储搜索方案，这里记为memo，key是(i, j)，value是一个布尔值，这里记为match，代表是否匹配。
在每次搜索前需要先进行3个条件判断，这3个条件判断的顺序尤为重要，不然过不了..
条件i). 首先判断p从j位置开始是否为空，若是且s从i位置开始同时也为空，则返回True，否则为False；
条件ii). 接下来判断(i, j)是否在memo里，若是，直接返回对应的value；
条件iii). 最后一个条件是判断s从i位置开始是否为空，若是，则需要p从j开始的后缀全为'*'，否则就返回False
OK，前置条件判断完，下面是搜索的内容。分两种情况：
i). 若p在j这个位置的字符是‘*’，那么对s在下一个位置i+1和p在当前位置进行搜索 或者 对p在下一个位置j+1和s在当前位置进行搜索，只要两者有其一返回True，则置当前结果为True；
ii). 若p在j这个位置的字符不是'*'，那么若想让当前匹配成功，则需要p在j这个位置的字符为'?‘ 或者 与s在i这个位置的字符相同，同时还需要对p在j+1位置开始与s在i+1位置开始进行搜索且返回True
最后，就是将当前结果存到memo，并返回。
2、dp（动态规划）
dp的代码写起来相对会简洁些，dp[i+1][j+1]代表s的前i个字符能否和p的前j个字符匹配，需要注意的是dp需要的空间是(n+1) x (m+1)，其中n、m分别是s和p的长度，因为需要dp[0][0]对应空字符串的情况，并且置为True。
在给dp赋值的时候，也是分两种情况：
i). 若 p[j] == '*'，则 dp[i+1][j+1] 为 dp[i][j+1] or dp[i+1][j] or dp[i][j]；
ii). 若 p[j] != '*'，那么 dp[i+1][j+1] 为 dp[i][j] and (p[j] == s[i] or p[j] == '?')
最终返回dp[n][m]即为所求。
代码
1、记忆化搜索
class Solution:
"""
@param s: A string
@param p: A string includes "?" and "*"
@return: is Match?
"""
def isMatch(self, s, p):
return self.helper(s, 0, p, 0, {})
def helper(self, s, s_idx, p, p_idx, memo):
"""判断s从s_idx开始的后缀和p从p_idx开始的后缀可否匹配"""
# 注意这个判断条件需要放置在最前面
# 当p的后缀为空时s的后缀也需要为空
if not p[p_idx:]:
return not s[s_idx:]
if (s_idx, p_idx) in memo:
return memo[(s_idx, p_idx)]
# 当s的后缀为空而p的后缀不为空时
# 则需要p的后缀全是'*'
if not s[s_idx:]:
p_set = set(p[p_idx:])
return len(p_set) == 1 and p_set.pop() == '*'
# 若p在当前位置是'*'，则可以令s在下一个位置和其在当前位置匹配
# 或者让其在下一个位置和s在当前位置匹配
if p[p_idx] == '*':
match = self.helper(s, s_idx + 1, p, p_idx, memo) or \
self.helper(s, s_idx, p, p_idx + 1, memo)
# 若p在当前位置不是'*'，则需要p和s的当前字符相同
# 或者p在当前位置是'?'，同时还需要两者的后缀匹配
else:
match = p[p_idx] in (s[s_idx], '?') and \
self.helper(s, s_idx + 1, p, p_idx + 1, memo)
memo[(s_idx, p_idx)] = match
return match
2、dp（动态规划）
class Solution:
"""
@param s: A string
@param p: A string includes "?" and "*"
@return: is Match?
"""
def isMatch(self, s, p):
n, m = len(s), len(p)
# dp[i+1][j+1]：s的前i个字符能否和p的前j个字符匹配
# 比字符串长度多1，dp[0][0]对应空字符串的情况
dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True
for j in range(1, m + 1):
dp[0][j] = dp[0][j - 1] and p[j - 1] == '*'
for i in range(n):
for j in range(m):
if p[j] == '*':
dp[i + 1][j + 1] = dp[i][j] or dp[i + 1][j] or dp[i][j + 1]
else:
dp[i + 1][j + 1] = dp[i][j] and p[j] in (s[i], '?')
return dp[n][m]
