0010-regular-expression-matching.go

funcisMatch(sstring, pstring) bool {
// dp[i][j] is true if p[:i] matches s[:j]
dp:=make([][]bool, len(p) +1)
fori:=0; i<len(p) +1; i++ {
dp[i] =make([]bool, len(s) +1)
forj:=0; j<len(s) +1; j++ {
dp[i][j] =false
 }
 }

dp[0][0] =true

// Base case for i = 0 is already set up, as empty pattern can only match empty string
// But a nonempty pattern can match an empty string, so we do base cases for j = 0
fori:=1; i<len(p); i++ {
ifp[i] =='*' {
dp[i+1][0] =dp[i-1][0]
 }
 }

// Now for the general case
fori:=0; i<len(p); i++ {
forj:=0; j<len(s); j++ {
ifp[i] =='.'||p[i] ==s[j] {
// Single character matches
dp[i+1][j+1] =dp[i][j]
 } elseifp[i] =='*' {
// Wildcard - check that the character matches
// or if we can have 0 repetitions of the previous char
dp[i+1][j+1] =dp[i-1][j+1] ||dp[i][j+1]
ifp[i-1] =='.'||p[i-1] ==s[j] {
ifdp[i+1][j] {
dp[i+1][j+1] =dp[i+1][j]
 }
 }
 }
 }
 }

returndp[len(p)][len(s)]
}