Home

# 实现正则表达式中的 . 和 * 的功能

.  匹配任意一个字符
*  匹配0个或多个*前面一个字符

动态规范的解法：

建立匹配的状态转移方程，设存在待匹配字符串 str 和模式字符串 pat， dp[i][j] 表示 截止到str[i-1] 位置的子串与截止到 pat[j-1] 位置的模式子串匹配的结果

# 边界条件

dp[0][j] 表示空字符串与模式子串匹配结果， dp[i][0] 表示字符子串与空模式子串匹配结果， dp[i][j] 表示空子串与空模式串匹配结果

dp[0][0] 一直为 true
dp[i][0](i > 0) 一直为 false, 因为任意非空子串与空模式串匹配不能匹配上
dp[0][j](j > 0) 的值需要看模式串 pat[j-1] 是否为 * ，如果是，则 * 可以选择匹配前一个字符 0 次，即 dp[0][j] = dp[0][j-2 ]

边界条件确认了之后，就可以缺点状态转移方程了

1
2
3
4
5
6
if str[i-1] == pat[j-1] or '.' == pat[j-1]
	dp[i][j] = dp[i-1][j-1]
else if pat[j-1] == '*'
	dp[i][j] = dp[i][j-2]
	if pat[j-2] == str[i]
		dp[i][j] |= dp[i-1][j]