44. 通配符匹配

题意：

解题思路：

状态定义：dp[i][j] : 表示 s 的前i个字符和p的前j个字符是否匹配(true的话表示匹配)
    状态转移方程：
        1. 当 s[i] == p[j]，或者 p[j] == ? 那么 dp[i][j] = dp[i - 1][j - 1];
        2. 当 p[j] == * 那么 dp[i][j] = dp[i][j - 1] || dp[i - 1][j]   
    其中：
        dp[i][j - 1] * 代表的是空字符，例如 ab, ab* //*可以代表空,匹配个数[0个]
        dp[i - 1][j] * 代表的是非空字符，例如 abcd, ab* //*代表cd,匹配个数[多个]
        dp[i - 1][j - 1] //abc ab* *代表c,匹配个数[1个]
    初始化：
        1. dp[0][0] 表示什么都没有，其值为 true
        2. 第一行 dp[0][j]，换句话说，s 为空，与 p 匹配，所以只要 p 开始为 * 才为 true
        3. 第一列 dp[i][0]，当然全部为 false

PHP代码实现：

class Solution {
    function isMatch($s, $p) {
        // 状态 dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
        $dp = [];
         // 初始化
        $dp[0][0] = true;
        for ($j = 1; $j <= strlen($p); $j++) {
            if ($p[$j - 1] == '*') {
                $dp[0][$j] = $dp[0][$j - 1];
            } else {
                $dp[0][$j] = false;
            }    
        }
        for ($i = 1; $i <= strlen($s); $i++) {
            $dp[$i][0] = false;
        }
        // 状态转移
        for ($i = 1; $i <= strlen($s); $i++) {
            for ($j = 1; $j <= strlen($p); $j++) {
                if ($s[$i - 1] == $p[$j - 1] || $p[$j - 1] == '?') {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1];
                } else if ($p[$j - 1] == '*') {
                    $dp[$i][$j] = $dp[$i][$j - 1] || $dp[$i - 1][$j] || $dp[$i - 1][$j - 1];
                } else {
                    $dp[$i][$j] = false;
                }
            }
        }
        return $dp[strlen($s)][strlen($p)];
    }
}

/* 贪心算法
        a    d    c    e    b 
        *    a    *    b
    1. $sBegin = 0 $pBegin = 0; j++
    2. $sBegin = 2 $pBegin = 1; j++
    3. j = b
    */
class Solution {
    function isMatch($s, $p) {
        return $this->isMatchDp($s, $p);
        $m = strlen($s);
        $n = strlen($p);
        $i = 0; $j = 0;
        $sBegin = -1; $pBegin = -1;
        while ($i < $m) {
            //两个字符相等或者p是问号
            if ($j < $n && $s[$i] == $p[$j] || $p[$j] == '?') {
                ++$i; ++$j;
            } else if ($j < $n && $p[$j] == '*') {//不等，但是p是星号
                ++$j;
                $sBegin = $i;
                $pBegin = $j;
            } else if ($pBegin != -1) {
                ++$sBegin;
                $i = $sBegin;
                $j = $pBegin;
            } else return false;
        }
        while ($j < $n && $p[$j] == '*') ++$j;
        return $j == $n;
    }
}

GO代码实现：

func isMatch(s string, p string) bool {
    sLen, pLen := len(s), len(p)
    dp := make([][]bool, sLen + 1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]bool, pLen + 1)
    }
    dp[0][0] = true
    for i := 1; i < pLen + 1; i++ {
        dp[0][i] = dp[0][i - 1] && p[i - 1] == '*'
    }
    for i := 1; i < sLen + 1; i++ {
        for j := 1; j < pLen + 1; j++ {
            if s[i - 1] == p[j - 1] || p[j - 1] == '?' {
                dp[i][j] = dp[i - 1][j - 1]
            } else if p[j - 1] == '*' {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 1][j - 1] 
            } else {
                dp[i][j] = false
            }
        }
    }
    return dp[sLen][pLen]
}