LeetCode-Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

在使用循环奋斗了 40 分钟以后，还是放弃了挣扎。

循环的思路大致就是使用两个指针描述在两个字符串中的当前匹配位置，然后对当前字符和下一个字符作分类讨论（是.、*还是普通字符），然后根据情况去调整指针的位置以完成匹配。

因为在出现.*的时候，如果不使用递归，作下一步判断是比较麻烦的（因为要分两种情况）。而且，循环中还出现了好几个比较麻烦的边界 bug，所以，这个问题就最好换用递归的思路来解了。

参考了 Solution 以后，写出如下递归算法（其实是一个状态机）。

比较有意思的地方是在遇见*的时候，需要分两种情况讨论，第一种是直接跳过当前的 pattern（匹配了 0 次），第二种是继续使用当前的 pattern 匹配后面的 string，当然，这时候要求首字符也匹配。

func judgeMatch(s []byte, p []byte) bool{
    if len(p)==0 {
        return len(s)==0
    }
    firstMatch:=false
    if len(s)>0 && (s[0]==p[0] || p[0]=='.') {
        firstMatch=true
    }
    if len(p)>1 && p[1]=='*' {
        return judgeMatch(s,p[2:]) || (firstMatch && judgeMatch(s[1:],p))
    }else{
        return firstMatch && judgeMatch(s[1:],p[1:])
    }
}
func isMatch(s string, p string) bool {
    return judgeMatch([]byte(s),[]byte(p))
}

使用动态规划，可以用一个数组来记录之前计算过的值，效率提高了很多。

但 go 不支持三元组 true,false 和 nil 匹配，所以只能使用一个数组代替，转换的过程可能会造成一些性能损失。

需要注意的是，申请 mem 数组的时候，需要比原来的长度多一个，不然会造成内存错误，这时因为要存储都匹配完成以后的值。

var (mem [][]int
     gs string
     gp string
    )
func judgeMatch(i int, j int) bool {
    if mem[i]==nil {
        mem[i]=make([]int,len(gp)+1)
    }
    if mem[i][j]==0 {
        var ans bool
        if j==len(gp) {
            ans=i==len(gs)
        }else{
            firstMatch:=false
            if i<len(gs) && (gs[i]==gp[j] || gp[j]=='.') {
                firstMatch=true
            }
            if j+1<len(gp) && gp[j+1]=='*' {
                ans=judgeMatch(i,j+2) || (firstMatch && judgeMatch(i+1,j))
            }else{
                ans=firstMatch && judgeMatch(i+1,j+1)
            }
        }
        if ans {
            mem[i][j]=1
        }else{
            mem[i][j]=2
        }
    }
    if mem[i][j]==1 {
        return true
    }
    return false
}
func isMatch(s string, p string) bool {
    mem=make([][]int,len(s)+1)
    gs=s
    gp=p
    return judgeMatch(0,0)
}

使用动态规划，能保留中间变量，还能可以将递归改为循环，非常厉害，需要多思考一下这种方法！

这里提供了一种解决这个问题的正向的思路和解法，非常值得参考。

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

这篇博客里面对动态规划讲的很不错。

动态规划问题需要满足三个原则:

最优化原理：最优解包含的子问题的解也是最优解。
无后效性：某阶段的状态一旦确定，此后过程不受前面各种状态的影响（类似一阶马尔可夫链）
重叠子问题：子问题之间不是独立的，一个子问题可能在之后决策中被多次利用（这个不是必要条件，但只有这个性质才能体现出动态规划算法的优势）——所以 DP 其实是一个以空间换时间的算法，为了降低时间复杂度，使用空间记录每个子问题的结果，以做到不对子问题进行重复的计算。

动态规划的求解过程：

划分阶段：将问题按照时间或空间特性划分为若干个阶段，划分后的阶段一定需要是有序的或者可排序的，否则问题无法求解。
确定状态和状态变量：将问题发展到各个阶段时所处的客观情况使用状态变量表示出来，当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：状态转移就是根绝上一阶段的状态和决策导出本状态的过程。所以可以通过相邻两个状态之间的关系来确定决策的方法和状态转移方程。
寻找边界条件：因为状态转移方程是一个递推方程，所以需要有一个终止条件或边界条件来结束递推。一般情况下，只要解决问题阶段的状态和状态转移确定了，就可以写出边界条件。