44. 通配符匹配
給定一個字符串 (s) 和一個字符模式 § ，實現一個支持 ‘?’ 和 ‘*’ 的通配符匹配。
'?' 可以匹配任何單個字符。
'*' 可以匹配任意字符串（包括空字符串）。
兩個字符串完全匹配才算匹配成功。
說明:
s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 ? 和 *。
示例 1:
輸入:
s = “aa”
p = “a”
輸出: false
解釋: “a” 無法匹配 “aa” 整個字符串。
示例 2:
輸入:
s = “aa”
p = ""
輸出: true
解釋: '’ 可以匹配任意字符串。
示例 3:
輸入:
s = “cb”
p = “?a”
輸出: false
解釋: ‘?’ 可以匹配 ‘c’, 但第二個 ‘a’ 無法匹配 ‘b’。
示例 4:
輸入:
s = “adceb”
p = “ab”
輸出: true
解釋: 第一個 ‘’ 可以匹配空字符串, 第二個 '’ 可以匹配字符串 “dce”.
示例 5:
輸入:
s = “acdcb”
p = “a*c?b”
輸出: false
數組定義
dp[i][j]代表s的前i個字符和p的前j個字符能否匹配
初始化
因為*可以匹配空字符串，所以在s的前部分只要是連續 *，就能一直匹配空字符串
狀態轉移
- p.charAt(j-1)==’?’||p.charAt(j-1)==s.charAt(i-1)
說明當前遍歷的兩個字符可以直接匹配，直接由dp[i-1][j-1]轉移過來 - p.charAt(j-1)==’*’
- *可以當成空字符串，所以可以由dp[i][j-1]轉移而來
- 在遍歷i-1的時候，*可能會變為一個通配字符串，使得s的i-1個字符和p的j個字符匹配，而 *是可以匹配任意字符串的，所以我們可以修改通配的字符串，使得第i個字符也在這個通配字符串里面，結果就從dp[i-1][j]轉移而來
代碼
class Solution {public boolean isMatch(String s, String p) {int n=s.length(),m=p.length();boolean[][] dp=new boolean[n+1][m+1];dp[0][0]=true;for(int i=1;i<=m;i++){if(p.charAt(i-1)=='*'){dp[0][i]=true;}else break;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(p.charAt(j-1)=='?'||p.charAt(j-1)==s.charAt(i-1))dp[i][j]=dp[i-1][j-1];else if(p.charAt(j-1)=='*'){dp[i][j]=dp[i-1][j] | dp[i][j-1];}}return dp[n][m];}
}
)
