题目描述
实现支持'.'和'*'的正则表达式匹配。
'.'匹配任意一个字母。
'*'匹配零个或者多个前面的元素。
匹配应该覆盖整个输入字符串，而不仅仅是一部分。
需要实现的函数是：bool isMatch(string s, string p)
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
测试样例
输入："aa"，"a"
输出：false
解释：
无法匹配
输入："aa"，"a*"
输出：true
解释：
'*' 可以重复 a
解题思路
个人感觉题目描述对于'*'字符的解释不太清晰，当大家看到 isMatch("aab", "c*a*b") → true 这个样例时，可能会一脸懵逼。其实'*'的意思是可以把位于其前面的字符删掉、保留或者复制多次。对于"c*ab"来说，其可以匹配"ab"（删掉c）、"cab"（保留一个c）、"ccc...cccab"（将c复制多个）。
OK，明确了以上这点，就可以真正下手了。哦不对，还不可以急着撸代码，先理清思路，和写作一样，不着急动手。
这种题的套路通常都是记忆化搜索，每次搜索s从位置i开始的后缀与p从位置j开始的后缀可否匹配。使用一个dict来记录存储的结果，记为memo，key是(i, j)，value是布尔值，代表能否匹配，在搜索过程中，分两种情况判断：
i). 当 j < len(p) - 1 且 p[j + 1] == '*' 时，若想要 s[i:] 和 p[j:] 匹配，则可以有两种方案：一种是 p[j] 等于 s[i] 或 '.'， 同时 s[i+1:] 与 p[j:] 能匹配。你们猜猜这里为何是将s后移即令 s[i+1:] 和 p[j:] 匹配，不告诉你哈哈哈...开个玩笑，因为 p[j + 1] 是 '*'，将s后移一位与p当前位置匹配的实际效果就是将 p[j] 复制了一次，如果在搜索过程中不断地将s后移那么就是将 p[j] 复制了多次，这种方式恰恰体现了 '*' 这个字符的“精华”。在这里容易“走错方向”的就是将 s[i + 1:] 与 p[j + 1:] 匹配，这看上去很合理，但实际上 p[ j + 1] 是 '*'，它是没有实际意义的字符，可以认为是不存在的，'*' 必须依赖其前一个字符，因此在这里当 p[j + 1] 是 '*' 时，不能将 s[i + 1:] 与 p[j + 1:] 匹配。个人认为，这点是整个解决方案中最重要的一点，也是成功最关键的一点！另一种方案就是不管 p[j] 与 s[i] 可否匹配上，将 s[i:] 与 p[j + 2:]进行匹配，就是说下一个字符 '*' 将当前的字符 p[j] 给删了。
ii). 这种情况就是不满足以上 i) 的情况，这时就按常规方式处理，若想要 s[i:] 和 p[j:] 匹配，则 p[j] 要等于 s[i] 或 '.'，同时 s[i + 1:] 和 p[j + 1:] 能匹配上。
搜索的主要过程就如以上 i) 和 ii)，除此之外，在进行以上提到的处理过程时，需要先依次进行3个条件判断：
1、若 (i, j) 在 memo 中，则直接返回memo[(i, j)]；
2、若 s[i:] 为空，那么需要对 p[j:] 的每个字符进行检查，若有字符不是 s[-1]、'*'、'.'，那么就返回False，否则返回True；
3、若 p[j:] 为空，则直接返回False，因为已经检查了 s[i:] 是否为空，能走到这一步说明 s[i:] 不为空，那么 p[j:] 却空了，就肯定匹配不成了嘛！
算法的整个过程如上阐述，接下来上代码咯！
代码
class Solution:
"""
@param s: A string
@param p: A string includes "." and "*"
@return: A boolean
"""
def isMatch(self, s, p):
if s and not p:
return False
if len(s) != len(p) and '*' not in p:
return False
return self.helper(s, 0, p, 0, {})
def helper(self, s, i, p, j, memo):
if (i, j) in memo:
return memo[(i, j)]
if not s[i:]:
return self.check(s, p[j:])
if not p[j:]:
return False
if j < len(p) - 1 and p[j + 1] == '*':
# 因为p在j+1位置的字符'*'可以理解为实际上是不存在的，
# 所以当p[j]为s[i]或'.'时，
# 需要s在i+1的位置与p在当前j位置开始匹配
# 剩下一种情况就是p[j]不为s[i]和'.'时，'*'可将前面的字符删除
# 因此可以令s在当前位置i与p在后两个位置开始匹配
match = (p[j] in (s[i], '.') and self.helper(s, i + 1, p, j, memo)) or \
(self.helper(s, i, p, j + 2, memo))
else:
# 当p在下一个位置不是'*'时，就需要p[j]与s[i]能匹配上，
# 并且两者在下一个位置也能匹配上
match = p[j] in (s[i], '.') and self.helper(s, i + 1, p, j + 1, memo)
memo[(i, j)] = match
return match
def check(self, s, p):
for ch in p:
if ch not in ('*', '.', s[-1]):
return False
return True
