[困难] 10. 正则表达式匹配

描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符

• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

代码

func isMatchV1(s string, p string) bool {
	return dfs(s, p, len(s)-1, len(p)-1)
}

func dfs(s, p string, i, j int) bool {
	if j < 0 {
		return i < 0
	}
	if p[j] == '*' {
		if i < 0 || (p[j-1] != '.' && p[j-1] != s[i]) {
			return dfs(s, p, i, j-2)
		}
		return dfs(s, p, i-1, j) || dfs(s, p, i, j-2)
	}
	if i < 0 {
		return false
	}
	if p[j] == '.' || s[i] == p[j] {
		return dfs(s, p, i-1, j-1)
	}
	return false
}