golang力扣leetcode 10.正则表达式匹配

1.定义dp[i][j]:在s串中前i位，p串中前j位，是否匹配成功
2.如果p能匹配当前字符，或者p为.  则dp[i][j] = dp[i-1][j-1]
3.如果p为*，则可以匹配0次或多次
4.如果dp[i][j-2]=true,说明匹配0次是成功的，匹配0次看前两位状态
5.如果不能匹配0次，说明需要匹配1次或多次，prev := p[j-2]
6.如果前一位字符prev匹配s的当前字符，或者prev=. ,则有机会匹配成功，如果不等于s的当前字符或不为. ，说明肯定不成功
7.有机会匹配成功dp[i][j] = dp[i-1][j]，需要看前一个字符是否匹配成功

func isMatch(s string, p string) bool {
  n := len(s) + 1
  m := len(p) + 1
  dp := make([][]bool, n)
  for i := range dp {
    dp[i] = make([]bool, m)
  }
  //空串匹配
  dp[0][0] = true
  //初始化边界，p与空串的匹配
  for i := 1; i < m; i++ {
    chP := p[i-1]
    if chP == '*' {
      dp[0][i] = dp[0][i-2]
    }
  }
  //dp开始
  for i := 1; i < n; i++ {
    chS := s[i-1]
    for j := 1; j < m; j++ {
      chP := p[j-1]
      //p能匹配当前字符，或者p为.
      if chP == chS || chP == '.' {
        dp[i][j] = dp[i-1][j-1]
      } else if chP == '*' { //p为前为*
        if dp[i][j-2] { //* 匹配0次，看前两位的状态
          dp[i][j] = true
        } else {
          prev := p[j-2]
          if prev == chS || prev == '.' {//p的前一位匹配当前字符，或p为.
            dp[i][j] = dp[i-1][j] //* 匹配一次或多次,看前一位的状态
          }
        }
      }
    }
  }
  return dp[n-1][m-1]
}