10. 正则表达式匹配

放弃吧，太难 ；细节太多，轮子哥还写过一个正则引擎

解题思路

  • 1、设定memo[indexStr][j]为s取前indexStr个字符，p取前indexPattern个字符时，是否匹配
  • 2、当s[indexStr]和p[indexPattern]匹配时，那么其结果继承前一项，即memo[indexStr-1][indexPattern-1]

那么怎么判断两边匹配呢？ 当p[indexPattern] == s[indexStr]，即两者字符一样，或者p[indexPatter]为.时，两边匹配，所以咱们可以写出这个方法，来判断匹配
// 字符串s和正则p当前元素是否匹配

  1. matches := func(sIndex, pIndex int) bool {
  2.     if sIndex < 1 {
  3.         return false
  4.     }
  5.     if p[pIndex-1] == '.' || s[sIndex-1] == p[pIndex-1] {
  6.         return true
  7.     }
  8.     return false
  9. }
  • 3、当s[indexStr]和p[indexPattern]不匹配时，就看p[indexPattern]是不是*号，这时候，分两种情况，一种是
    • 1）s: ab p: abc*这种，虽然p里面有c*，但是s里面可以一个c都没有，因为*可以匹配0个字符，那么匹配可以直接跳过p的最后两项
  • memo[indexStr][indexPattern] = memo[indexStr][indexPattern-2]
    • 2）abbb / ab.* 或 abbb / abb*这种，这时候，因为不知道到底能匹配多少个b，所以可以把结果托给前一项，即
  • memo[indexStr][indexPattern] = memo[indexStr-1][indexPattern]
    • 3）abbb / ac.*这种，直接不匹配了，因为memo对应项的值默认就是false，咱们可以不处理了
  • 4、注意base项，当indexStr/indexStr都是0时候，肯定匹配咯
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool,len(s)+1)

    for i:=0;i<=m;i++ {
        dp[i] = make([]bool,n+1)
    }

    dp[0][0] = true
    for i := 0;i <= m; i++ {
        for j := 1;j <= n; j++ {             //防止其越界，从1开始
            if p[j-1] == '*' {
                if i!=0 && (s[i-1] == p[j-2] || p[j-2] == '.') {
                    dp[i][j] = dp[i][j] || dp[i][j-2] || dp[i-1][j] || dp[i-1][j-2] 
                } else {
                    dp[i][j] = dp[i][j] || dp[i][j-2]             //前一个字符没有匹配上，直接匹配零个
                }
            } else if i != 0 && (s[i-1] == p[j-1] || p[j-1] == '.') {
                dp[i][j] = dp[i][j] || dp[i-1][j-1]                //前一个字符匹配相同，或者模式为.时，只匹配一个字符
            }
        }
    }
    return dp[m][n]
}

//二维，时空Omn
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    matches := func(i, j int) bool {
        if i == 0 {
            return false
        }
        if p[j-1] == '.' {
            return true
        }
        return s[i-1] == p[j-1]
    }

    f := make([][]bool, m + 1)
    for i := 0; i < len(f); i++ {
        f[i] = make([]bool, n + 1)
    }

    f[0][0] = true
    for i := 0; i <= m; i++ {
        for j := 1; j <= n; j++ {

            if p[j-1] == '*' {
                f[i][j] = f[i][j] || f[i][j-2]
                if matches(i, j - 1) {
                    f[i][j] = f[i][j] || f[i-1][j]
                }

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