剑指offer—面试题19：正则表达式匹配

请实现一个函数用来匹配包含'. '和''的正则表达式。模式(p :String)中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串(s :String)的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

该题并不需要你懂太多的正则表达式知识，看的动题目就行。但是如果知道正则表达式的规则的可以帮助你快速列出需要匹配的可能情况。

我们首先列出匹配的可能性假设主串为 A，模式串为 B 从最后一步出发，需要关注最后进来的字符。假设 A 的长度为 n ，B 的长度为 m ，关注正则表达式 B 的最后一个字符是谁，它有三种可能，正常字符、*∗ 和 .（点），那针对这三种情况讨论即可，如下：

1. 如果 BB 的最后一个字符是正常字符，那就是看 A[n-1] 是否等于 B[m-1]，相等则看 A{0..n-2} 与 B{0..m-2}，不等则是不能匹配，这就是子问题。
2. 如果 B 的最后一个字符是.，它能匹配任意字符，直接看 A{0..n-2} 与 B{0..m-2}
3. 如果 B 的最后一个字符是*它代表 B[m-2]=c可以重复0次或多次，它们是一个整体 c∗

• 情况一：A[n-1] 是 0 个 c，B 最后两个字符丢弃，能否匹配取决于 A{0..n-1}和 B{0..m-3}
• 情况二：A[n-1]是多个 c 中的最后一个（这种情况必须 A[n-1]=c或者 c='.'，所以 A匹配完往前挪一个，B 继续匹配，因为可以匹配多个，继续看 A{0..n-2}和 B{0..m-1}是否匹配。

class Solution {
    func isMatch(_ s: String, _ p: String) -> Bool {
        let n = s.count
        let m = p.count
        
        var dp = Array(repeating: Array(repeating: false, count: m+1), count: n+1)
        
        // 字符串转为数组，方便后面操作
        let s = Array(s)
        let p = Array(p)
        
        for i in 0...n {
            for j in 0...m {
                // 空正则的情况
                if j == 0 {
                    dp[i][j] = (i==0)
                }else {
                    let pj = p[p.index(p.startIndex, offsetBy: j-1)]
                    // 非空正则
                    if pj != "*" {
                        if i > 0 && (s[s.index(s.startIndex, offsetBy: i-1)] == pj ||  pj == "." ){
                            dp[i][j] = dp[i-1][j-1]
                        }
                    }else {
                        if j >= 2 {
                            dp[i][j] =  dp[i][j]  || dp[i][j-2]
                        }
                        
                        if i >= 1 && j >= 2 && (s[s.index(s.startIndex, offsetBy: i-1)] == p[p.index(p.startIndex, offsetBy: j-2)] ||  p[p.index(p.startIndex, offsetBy: j-2)] == ".") {
                            dp[i][j] =  dp[i][j] || dp[i-1][j]
                        }
                        
                    }
                }
            }
        }
        return dp[n][m]
    }
}