题解 | #正则表达式匹配#

import "strconv"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @param pattern string字符串 
 * @return bool布尔型
*/
func match( s string ,  p string ) bool {
    return dp(s, 0, p, 0)
}
func dp(s string,  i int, p string, j int) bool {
    m, n := len(s), len(p)
    if j == n {
        return i == m
    }
    if i == m {
        if (n-j) % 2 == 1 {
            return false
        }
        for ; j + 1 < n; j += 2 {
            if p[j+1] != '*' {
                return false
            }
        }
        return true    
    }
    key := strconv.Itoa(i) + "," + strconv.Itoa(j)
    memo := map[string]bool{}
    if memo[key] == true {
        return memo[key]
    }
    res := false
    if s[i] == p[j] || p[j] == '.' {
        if j + 1 < n && p[j+1] == '*' {
            res = dp(s, i, p, j+2) || dp(s, i+1, p, j)
        }else {
            res = dp(s, i+1, p, j+1)
        }
    }else {
        if j + 1 < n && p[j+1] == '*' {
            res = dp(s, i, p, j+2)
        }else {
            return false
        }
    }
    memo[key] = res
    return res
}