Hard
fb tag
https://www.youtube.com/watch?v=DqhPJ8MzDKM
此題簡稱為"p中找s", 用dp做。
這道題一開始我naive地覺得如果p.length() < s.length()則一定return false. 然而*的含義是零個(gè)或多個(gè)它前面的字符,所以完全可能p的長度沒有s長触机，因?yàn)?code>*可以控制字符數(shù). 這里我們assume *只可能出現(xiàn)在charAt(i) i >= 1.
dp[i][j]表示s.substring(0, i)跟p.substring(0, j)是不是匹配畜普，也就是s里面前i個(gè)字符跟p里面前j個(gè)字符是否匹配砸脊。
首先dp[0][0] = true,因?yàn)閮蓚€(gè)空字符是相匹配的涡匀。
至于我們?yōu)槭裁匆獑为?dú)把dp[0][i]單獨(dú)拿出來初始化拴事，是因?yàn)楹竺娈?dāng)i >= 1, j >= 1的時(shí)候蒋伦，我們要用到dp[i-1][j-1]這樣的前面的狀態(tài)弓摘，而dp[0][something]帶入到這里的話就會(huì)越界。同樣很intuitive的我們可以知道dp[something][0] = false, 因?yàn)樵诳兆址锩婺阍趺凑乙舱也坏絪. 所以就不單獨(dú)initialize了痕届。

那么中間的部分韧献，我們分兩種大類討論。

• 斜線（對角線）遞推
• 直線（左到右研叫，上到下）遞推

斜線遞推是說當(dāng)p.charAt(j-1) == s.charAt(i-1)時(shí)锤窑，或者p.charAt(j-1) == '.'時(shí)，我們的dp[i][j] = dp[i-1][j-1], 就相當(dāng)于一條斜線從左上角i-1,j-1穿到了i,j.
直線遞推是當(dāng)p.charAt(j-1) == *時(shí)嚷炉，我們可以選擇讓它代表前面的字符一共0個(gè)或者多個(gè)渊啰。當(dāng)它代表前面的字符零個(gè)的時(shí)候，我們就相當(dāng)于把p刪掉了后面兩個(gè)字符，所以dp[i][j] = dp[i][j-2]. 當(dāng)它代表前面的字符有多個(gè)的時(shí)候绘证，我們要考慮一種特殊情況隧膏，就是當(dāng)p.charAt(j-2) == s.charAt(i-1), 也就是p倒數(shù)第二個(gè)字符（倒數(shù)第一個(gè)是*)等于s的倒數(shù)第一個(gè)字符，或者p的倒數(shù)第二個(gè)字符干脆就是任意字符.,這種情況dp[i][j] = dp[i-1][j], 也就是如果這時(shí)候s除去最后一個(gè)字符剩下的部分跟p匹配的話嚷那，因?yàn)?code>*可以讓p繼續(xù)添加一個(gè)當(dāng)前最后的字符胞枕，而這個(gè)字符又剛好等于s的最后一個(gè)字符，所以他們會(huì)繼續(xù)匹配魏宽，因此此時(shí)dp[i][j] = dp[i-1][j]. 比如p = ab*, s = abb, 這時(shí)候就可以得到dp[3][3] = dp[2][3]. 但是這種情況我們不能直接就不考慮 *代表零個(gè)了腐泻，而是只要其中一種匹配就return true.
這個(gè)test case可以測出來必須兩個(gè)都寫：
"aaa"
"ab*a*c*a"

class Solution {
    public boolean isMatch(String s, String p) {
        if (p == null || s == null){
            return false;
        }   
        //"aaa"
        //".*"
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        //dp[i][j]: s.substring(0, i) matches with p.substring(0, j); i,j means number of characters,not index.
        dp[0][0] = true; //"" matches ""
        
        for(int i = 1; i < p.length() + 1; i++){
            if (p.charAt(i-1) == '*'){
                dp[0][i] = dp[0][i-2];
            }
        }
        
        for (int i = 1; i < s.length() + 1; i++){
            for (int j = 1; j < p.length() + 1; j++){
                if (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.'){
                    dp[i][j] = dp[i-1][j-1];
                } else if (p.charAt(j-1) == '*'){
                    //"*" could means zero or multiple
                    if (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'){
                        dp[i][j] = dp[i-1][j] || dp[i][j-2];
                    } else {
                        dp[i][j] = dp[i][j-2];
                    }
                }                
            }
        }
        return dp[s.length()][p.length()];
    }
}