LeetCode: Regular Expression Matching

// https://code.dennyzhang.com/regular-expression-matching
// Basic Ideas: dynamic programming
//
// Notice: fast fail doesn't work
// Notice: how to treat * in pattern, when it means multiple copies
//
// Complexity: Time O(n*m), Space O(n*m)
func isMatch(s string, p string) bool {
    dp := make([][]bool, len(s)+1)
    for i, _ := range dp {
        dp[i] = make([]bool, len(p)+1)
    }
    dp[0][0] = true
    for i:=0; i<len(p); i++ {
        // When *, check the previous previous node
        if p[i] == '*' && dp[0][i-1] {
            dp[0][i+1] = true
        }
    }
    // dp
    for i:=0; i<len(s); i++ {
        for j:=0; j<len(p); j++ {
            // caculate dp[i+1][j+1]
            // same characters or .
            if s[i] == p[j] || p[j] == '.' {
                dp[i+1][j+1] = dp[i][j]
            }
            if p[j] == '*' {
                if p[j-1] != s[i] && p[j-1] != '.' {
                    // need to treat as repeating 0 times
                    dp[i+1][j+1] = dp[i+1][j-1]
                } else {
                    // treat it as repeating 0 times, 1 times and multiple times
                    dp[i+1][j+1] = dp[i+1][j-1] || dp[i+1][j] || dp[i][j+1]
                }
            }
        }
    }
    return dp[len(s)][len(p)]
}