Regular Expression Matching

.go

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

const (
    dot = byte('.')
    asterisk = byte('*')
)