golang刷leetcode动态规划（6）正则表达式

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

输出: false

func isMatch(s string, p string) bool {
  if len(s) == 0 && len(p) == 0 {
    return true
  }
  if len(p) == 0 {
    return false
  }
  if len(s) == 0 {
    if len(p)%2 != 0 {
      return false
    }
    for i := 1; i < len(p); i += 2 {
      if []byte(p)[i] != '*' {
        return false
      }
    }
        return true
  }
  bs := []byte(s)
  bp := []byte(p)
  a := make([][]bool, len(s)+1)
  for i := 0; i < len(s)+1; i++ {
    a[i] = make([]bool, len(p)+1)
  }
  a[0][0] = true
  a[1][1] = match(bs[0], bp[0])
  for j := 2; j < len(p)+1; j = j + 2 {
    a[0][j] = a[0][j-2] && bp[j-1] == '*'
  }

  for i := 1; i < len(s)+1; i++ {
    for j := 2; j < len(p)+1; j++ {
      if bp[j-1] == '*' {
        //0  1
        a[i][j] = a[i][j-2] || (a[i-1][j-1] && match(bs[i-1], bp[j-2])) || (a[i][j-1] && match(bs[i-1], bp[j-2])) || (a[i-1][j] && match(bs[i-1], bp[j-2]))
      } else {
        a[i][j] = a[i-1][j-1] && match(bs[i-1], bp[j-1])
      }
    }
  }

  return a[len(s)][len(p)]

}

func match(a, b byte) bool {
  return a == b || b == '.'
}