一般这种问题都往动态规划的方面去考虑。
所谓动态规划，最重要的就是得找到当前节点和前面之间的关系，写出来递推表达式，基本就求出来了。
这个题中，.代表任意一个字符，*匹配零个或多个前面的元素。
递归
情况一：下一个字符是* ，那就又分成两种情况，* 代表0个或者多个。代表0个的时候，说明* 没有用了，下一个pattern就需要跳过当前字符和下一个* ，所以是isMatch(text, pattern[2:])。匹配多个的话，那么需要检查当前text字符是否匹配first_match，以及text中的下一个字符是否符合当前pattern：isMatch(text[1:], pattern)。
情况二：下一个字符不是* ，那么只要看text和pattern当前的字符是否匹配就行了。
class Solution(object):
def isMatch(self, text, pattern):
if not pattern:
return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
if len(pattern) >= 2 and pattern[1] == '*':
return (self.isMatch(text, pattern[2:]) or
first_match and self.isMatch(text[1:], pattern))
else:
return first_match and self.isMatch(text[1:], pattern[1:])
动态规划
我的理解是，动态规划和递归原理上是相同的，都是通过找到当前节点和下一个或者前一个节点之间的关系来实现，只是在递归的过程中，会发现有很多重复计算的过程，所以时间复杂度是指数级别的。因此对于那些重复算过的，其实我们可以不用在重复递归来算它的，可以把中间结果给保存起来，这种就是动态规划的思想。
要注意的就是边界条件。
class Solution(object):
def isMatch(self, text, pattern):
memo = {}
def dp(i, j):
if (i, j) not in memo:
if j == len(pattern):
ans = i == len(text)
else:
first_match = i < len(text) and pattern[j] in {text[i], '.'}
if j+1 < len(pattern) and pattern[j+1] == '*':
ans = dp(i, j+2) or first_match and dp(i+1, j)
else:
ans = first_match and dp(i+1, j+1)
memo[i, j] = ans
return memo[i, j]
return dp(0, 0)
想要dp[j][i]为1，需要满足下面两个条件中的任意一个：
1、dp[j-2][i] = 1,此时* 代表空串
(注：text不变，如果当前是空串，那么说明pattern[j-2]和pattern[j]都能匹配这个text，所以有如上结论。)
2、dp[j][i-1] = 1 且 pattern字符串j-2位置的字符和目标字符串i-1位置的字符相同(因为0位置表示了空串，所以数组中i位置代表的是字符串中的i-1位置)或者说pattern字符串j-2位置的字符为'.',此时'*'表示对前一个字符的复制。
class Solution(object):
def isMatch(self, text, pattern):
dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]
dp[-1][-1] = True
for i in range(len(text), -1, -1):
for j in range(len(pattern) - 1, -1, -1):
first_match = i < len(text) and pattern[j] in {text[i], '.'}
if j+1 < len(pattern) and pattern[j+1] == '*':
dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
else:
dp[i][j] = first_match and dp[i+1][j+1]
return dp[0][0]
网友评论