LeetCode--10. 正则表达式匹配

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符

• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

---

难，隔了四个月，终究还是一点记不得了，看着题解写的，说一下自己的理解：

由于我们需要一个初始状态，多开辟一组空间，来保存我们的初始状态，方便进行状态转移，然后需要开始dp。

依次遍历每个字符，如果当前正则表达式的字符为'*'，这说明而如果它前面的字符为x，那么它可以匹配任意长度，包括0的x子串，于是我们的方程就应该是f[i][j] = f[i][j] || f[i][j - 2]，为什么是j - 2的原因，在注释中标出来了。

而这仅仅是匹配了我们的前前个字符，并不能覆盖所有的情况，因为如果我们的当前正则表达式的*前面一个字符刚好能够匹配当前需要被匹配的字符串(s)，这确实无法通过上面那一步判断出来的，所以还需要加一步判断。

另外一种情况就是，当前遍历到的正则表达式字串不为*，那么就直接匹配我们的字符串，状态转移即可。

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]bool, m + 1)
    for i := 0; i <= m; 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] == '*' {
                //为什么是j - 2？
                //因为'x*'可以匹配0个或者任意一个'x'
                //所以只需要前前一个匹配即可
                f[i][j] = f[i][j] || f[i][j - 2]
                if match(i, j - 1, s, p) {
                    //当然，如果和'*'前一个字符匹配，也是一种情况
                    //此时就应该是i - 1，而不是i了
                    f[i][j] = f[i][j] || f[i - 1][j]
                }
            } else if match(i, j, s, p) {
                //如果匹配，根据前一个状态转移
                f[i][j] = f[i][j] || f[i - 1][j - 1]
            }
        }
    }
    return f[m][n]
}

//这里是i或者j - 1的原因是我们的dp对应的 数组第0位被占用，所以
//向后移了一位。对应到字符串上，则需要减回去
func match(i, j int, s, p string) bool {
    if i == 0 {
        return false
    }
    if p[j - 1] == '.' {
        return true
    }
    return s[i - 1] == p[j - 1]
}

经典 hard，二战过了：

func isMatch(s string, p string) bool {
    n, m := len(s), len(p)
    f := make([][]bool, n + 1)
    for i := 0; i <= n; i ++ {
        f[i] = make([]bool, m + 1)
    }
    f[0][0] = true
    for i := 0; i <= n; i ++ {
        for j := 1; j <= m; j ++ {
            if p[j - 1] == '*' {
                f[i][j] = f[i][j - 2] || f[i][j]
                if i > 0 && (p[j - 2] == '.' || s[i - 1] == p[j - 2]) {
                    f[i][j] = f[i - 1][j] || f[i][j]
                }
            } else if i > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                f[i][j] = f[i - 1][j - 1] || f[i][j]
            }
        }
    }
    return f[n][m]
}