题目来源：LC 10

这是道困难题，不能小看它。

首先，如果匹配里面没有 * ，这道题其实非常简单，只要一一对比两个字符是否匹配就可以了。其验证代码也非常好写：

def match(x, y):
	return (x == y or y == '.') and (y != '*')

下面考虑 * 的情况。事实上，* 和它前面字符一定是需要绑定处理的。否则无法处理 ".*" 这种字符串，因为它可以匹配成任意字符任意长度的字符串。

动态规划

我们令 f[i][j] 为一个布尔变量，等于 s 中前 i 个字符，p 中前 j 个字符是否匹配。

那么在没有 * 的情况下，

if match(s[i], p[j]):
	f[i][j] = f[i-1][j-1] 

如果考虑 * 的情况，

# *只会在p中出现
if p[j] == '*':

	# 如果*前面的字符（即p[j-1]）和s[i]相等
  # 那么可以忽略s[i]，考虑s[i-1]和p[j-1]是否匹配
	if match(s[i], p[j-1]):
  	f[i][j] = f[i-1][j]

	# 或者，不对p[j-1]和p[j]进行匹配，直接扔掉
	f[i][j] = f[i][j-2] or f[i][j]

以上是简略版的动态转移方程。

下面是完整代码：

def isMatch(self, s: str, p: str) -> bool:
        
	# 匹配函数
	def match(x, y):
		return (x == y or y == '.') and (y != '*')

	# 初始化
	f = [[False for j in range(len(p)+1)] for i in range(len(s)+1)]
	# 两个空字符串是匹配的
	f[0][0] = True

	for i in range(0,len(s)+1):
		for j in range(1,len(p)+1):
    
			# 如果s和p字符匹配
			if i >= 1 and match(s[i-1], p[j-1]):
				f[i][j] = f[i-1][j-1]

			# 如果有*
			if p[j-1] == '*':
			# 将p[j-1]和p[j]直接扔掉
				f[i][j] = f[i][j-2]
				# 如果p和s匹配，不考虑s中最后一个字符
				if i >= 1 and match(s[i-1], p[j-2]):
					f[i][j] = f[i-1][j] or f[i][j]

	return f[len(s)][len(p)]

复杂度分析：

• 时间上：代码中有两层循环，即时间复杂度是 O(mn)。
• 空间上：用了一个二维数组，即空间复杂度为 O(mn)。实际上空间复杂度可以优化一下。注意到，我们求 f[i][j] 时，只用了 f[i][:] 和 f[i-1] [:] ，因此其他已经存储空间可以释放出来，即空间复杂度可以优化为 O(n)。