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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @param pattern string字符串 
 * @return bool布尔型
*/
func match(str string ,pattern string ) bool {
    // write code here

    n := len(str)
    m := len(pattern)
    dp := make([][]int, n+1)
    for i:=0;i<n+1;i++{
        dp[i] = make([]int, m+1)
        for j:=0;j<m+1;j++{
            dp[i][j] = 0
        }
    }
    dp[0][0] = 1

    var match_sub func(i, j int) bool
    match_sub = func(i, j int) bool {
        if i==0 {
            return false
        }
        if pattern[j-1] == '.' {
            return true
        }
        return str[i-1] == pattern[j-1]
    }

    for i:=0;i<n+1;i++{
        for j:=1;j<m+1;j++{

            if pattern[j-1] == '*' {
                dp[i][j] |= dp[i][j-2]

                if match_sub(i, j-1){
                    dp[i][j] |= dp[i-1][j]
                }

            }else{
                if match_sub(i, j) {
                    dp[i][j] |= dp[i-1][j-1]
                }
            }
        }
    }
    return dp[n][m]==1
}