leetcode-go/leetcode/hard/10.regular-expression-matching.go

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	// dp[i][0] = false, if i > 0
	for i := 1; i <= n; i++ {
		dp[0][i] = 1 < i && p[i-1] == '*' && dp[0][i-2]
	}
	// dp[i][j] = if p[j-1] == '*', dp[i][j-2] || ((p[j-2] == '.' || s[i-1] == p[j-2]) && dp[i-1][j])
	//            else, (p[j-2] == '.' || s[i-1] == p[j-1]) && dp[i-1][j-1]
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '*' {
				dp[i][j] = dp[i][j-2] || ((p[j-2] == '.' || s[i-1] == p[j-2]) && dp[i-1][j])
			} else {
				dp[i][j] = (p[j-1] == '.' || s[i-1] == p[j-1]) && dp[i-1][j-1]
			}
		}
	}
	return dp[m][n]
}