10. 正则表达式匹配

题意

图示：

1. *代表一个字符的情况

2. * 代表一个字符的情况

1. * 代表多个字符的情况

解题思路：

思路：
    状态定义：dp[i][j] 表示 s 的前 i 个字符是否能被 p 的前 j 个字符匹配
    转移方程：
    * sc = s[i - 1] pc = p[j - 1]
    1. sc == pc|| pc == '.'
        1.1 '.'是万能字符，可以直接让'.'等于s[i]处的字符
            即：dp[i][j] = dp[i-1][j-1]; 
    2.    sc != pc || pc == '*' 分3种情况考虑
        2.1 '*'代表0个字符
            例子：s:aab, p:aabb*,重复0个b，相当于直接删去j-1(*)和j-2(b),最终要比较的是s(0...i-1)~p(0...j-3) 
            即：dp[i][j] = dp[i][j-2]
        2.2 '*'代表1个字符
            例子：s:aab, p:aab* (取1个字符，相当于去掉p[j-1]),只需要比较s(0...i-1)~p(0...j-2)
            即：dp[i][j] = dp[i][j-1] 
        2.2 '*'代表多个字符
            例子：s：aab, p：aab* => s:aab, p：aab*b 因为s的最后一个字符b等于p的最后一个字符，可以相互抵消，所以只需要比较 s(0...i-2)~p(0...j-1)即aa跟aab*比较
            即：dp[i][j] = dp[i-1][j] 
    3. sc != pc : 当i,j处是普通字符时，自然不相等
        即：dp[i][j] = false

初始化：
    1. s,p都为空串时则相匹配=》dp[0,0] = true;
    2. s不为空串，模式串p为空串时=》dp[i,0] = false, i >= 1
    3. s为空串，模式串p不为空串时，需要考虑p为*号的情况
        3.1 如果p最后一个字符p[j-1] == '*'，则可以用*把他前面字符重复0次，即消除前面字符，推出=》dp[0, j] = dp[0, j - 2]
        3.2 如果p最后一个字符p[j-1] != '*',则不相等，即dp[0, j] = false

PHP代码实现：

class Solution {
    function isMatch($s, $p) {
        //if ($s == null || $p == null) return false;
        $m = strlen($s);
        $n = strlen($p);
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, false));
        $dp[0][0] = true;
        for ($i = 1; $i <= $m; $i++) $dp[$i][0] = false;
        //s为空串，p不是空串的初始化
        for ($j = 1; $j <= $n; $j++) {
            //$p[$j - 1] == '*'，消除j前面的字符
            if ($p[$j - 1] == '*') $dp[0][$j] = $dp[0][$j - 2];
            else $dp[0][$j] = false;
        }
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                $sc = $s[$i - 1];
                $pc = $p[$j - 1];
                if ($this->isEqual($sc, $pc)) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1];
                } else if ($pc == '*') {
                    $preChar = $p[$j - 2];
                    if ($this->isEqual($sc, $preChar)) {
                        $dp[$i][$j] = $dp[$i][$j - 2] || $dp[$i][$j - 1] || $dp[$i - 1][$j];
                    } else $dp[$i][$j] = $dp[$i][$j - 2];
                } else {
                    $dp[$i][$j] = false;
                }
            }
        }
        return $dp[$m][$n];
    }
    function isEqual($sc, $pc) {
        return $sc == $pc || $pc == '.';
    }
}

GO代码实现：