這題是《劍指Offer》的原題，在LeetCode上屬于hard難度尊惰，雖然面試可能不會考到這種題目，但能夠很好地訓練自己的思維~
書中的解法是遞歸白华，但因為沒有剪掉重復問題的結果蓉冈，導致時間開銷巨大方妖，LeetCode上測試大概3秒匣缘，相比之下窘哈，動態(tài)規(guī)劃只用了3ms澄成，這也足以看出動態(tài)規(guī)劃的剪枝對減少運行時間的作用是巨大的滑黔。
首先分析這道題為什么是動態(tài)規(guī)劃：例如，s = "abc" p = "abc"环揽，我們會從前向后逐個檢查s和p中對應的位置是不是相等略荡，如果相等就檢查下一個位置，所以大問題的結果可以看成去掉結尾字符的子串是否匹配和結尾是否匹配的組合歉胶，因此汛兜，這是個動態(tài)規(guī)劃問題。
既然是動態(tài)規(guī)劃問題通今，那就要確定狀態(tài)粥谬，因為*的存在，s和p能夠在長度不相等的情況下匹配辫塌，所以漏策，要用一個二維數(shù)組記錄狀態(tài)：dp[i][j]表示s的前i個字符能否匹配上p的前j個。
選定狀態(tài)后臼氨，要先確定最小子問題的結果掺喻，也就是初值，有了初值储矩，才能自下向上逐步計算更大子問題的結果感耙。初值有以下三種情況：
-
dp[0][0] = true，s和p的前0個元素一定是可以匹配的持隧，畢竟兩個空集相等嘛~ -
dp[0][j]：比如即硼，s為空，p = "a*"時能匹配屡拨，即dp[0][2] == true只酥，這是因為p[1] == '*'，一個星號讓它前面的字符消失呀狼，同時dp[0][0] == true裂允，所以dp[0][2] == true。進行邏輯抽象后表述：只有當dp[0][j-2] == true且p[j-1] == '*'時赠潦，dp[0][j] = true; -
dp[i][0]：s不為空叫胖，p為空，這種情況無論如何都不能匹配她奥，所以全是false瓮增。
int row = s.length();
int col = p.length();
boolean[][] dp = new boolean[row+1][col+1];
dp[0][0] = true;
for(int j = 1; j <= col; j++){
if(p.charAt(j-1) == '*' && j >= 2 && dp[0][j-2]){
dp[0][j] = true;
}
}
接下來就到了最難的狀態(tài)轉(zhuǎn)移方程環(huán)節(jié)，由于*的存在會讓問題變得復雜哩俭，我們按照p[j-1]是否為*來分類討論：
-
p[j-1] != '*'
1.1p[j-1] == s[i-1]绷跑，兩個字符串的最后一位相等，則結果要由前面的子串判斷凡资，即：dp[i][j] = dp[i-1][j-1]砸捏；
1.2p[j-1] == '.'，因為.可以匹配任一字符隙赁，和情況1.1是等價的垦藏，因此，結果依然是dp[i][j] = dp[i-1][j-1]伞访；
1.3p[j-1] 掂骏！= s[i-1]，直接讓dp[i][j] = false厚掷，不解釋~ -
p[j-1] == '*'
2.1p[j-2] == s[i-1] || p[j-2] == '.'弟灼，即*號前的字符和s[i-1]相等（.也可以認為是相等），還要再分為三種情況討論冒黑，以下三種情況只要有一個符合就可以：
2.1.1*不匹配字符：s = "ab" p = "abb*"田绑，s的前兩位已經(jīng)和p的前兩位匹配了，*只需要讓前面的字符消失即可抡爹，即dp[i][j] = dp[i][j-2]掩驱；
2.1.2*匹配1個字符：s = "aab" p = "aab*"，此時的b*需要轉(zhuǎn)換成b冬竟，因此昙篙，dp[i][j] = dp[i][j-1]；
2.1.3*匹配多個字符：s = "aabb" p = "aab*"诱咏，這時的b*需要轉(zhuǎn)換成bb苔可，也相當于在s末尾去掉一個b，即dp[i][j] = dp[i-1][j]袋狞；
2.2p[j-2] != s[i-1]焚辅，也就是s = "a" p = "b*"這種情況，只能去掉b*苟鸯，因此同蜻，dp[i][j] = dp[i][j-2]。
最終的代碼：
class Solution {
public boolean isMatch(String s, String p) {
if(s == null || p == null) return false;
int row = s.length();
int col = p.length();
boolean[][] dp = new boolean[row+1][col+1];
//狀態(tài)矩陣初始化
dp[0][0] = true;
for(int j = 1; j <= col; j++){
if(p.charAt(j-1) == '*' && j >= 2 && dp[0][j-2]){
dp[0][j] = true;
}
}
for(int i = 1; i <= row; i++){
for(int j = 1; j <= col; j++){
//p[j-1] != '*'的情況
if(p.charAt(j-1) != '*'){
if(p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.'){
dp[i][j] = dp[i-1][j-1];
}
//p[j-1] == '*'的情況
}else{
//以下的情況都有j-2
if(j >= 2){
if(p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'){
dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
}else{
dp[i][j] = dp[i][j-2];
}
}
}
}
}
return dp[row][col];
}
}
最終結果：
