44.Wildcard Matching
题目链接：https://leetcode.com/problems/wildcard-matching/description/
题目大意：通配符匹配，与第10题的正则匹配类似，规则有所区别。'?'可以代替任意一个字符，'*'可以代替任意一个字符串。
法一（借鉴）：略难，不是特别懂。解释：https://www.cnblogs.com/boring09/p/4246055.html，代码如下（耗时74ms）：
1 public boolean isMatch(String s, String p) { 2 //sCurPos：s当前下标 3 //pCurPos：p当前下标 4 //pStarPos：p的最后一个*的下标 5 //sMatch：s与p的*匹配的最后一个字符的下标 6 int sCurPos = 0, pCurPos = 0, pStarPos = -1, sMatch = 0; 7 while(sCurPos < s.length()) { 8 System.out.println("sCurPos:" + sCurPos + ",pCurPos:" + pCurPos + ",pStarPos:" + pStarPos + ",sMatch:" + sMatch); 9 //如果s当前字符==p当前字符或p当前字符是?，则s和p同时往后挪一位 10 if(pCurPos < p.length() && (s.charAt(sCurPos) == p.charAt(pCurPos) || p.charAt(pCurPos) == '?')) { 11 sCurPos++; 12 pCurPos++; 13 } 14 //如果p当前字符是*，则记录p此时*的下标，并且记录s此时匹配的位置下标，p往后挪一位 15 else if(pCurPos < p.length() && p.charAt(pCurPos) == '*') { 16 pStarPos = pCurPos; 17 sMatch = sCurPos; 18 pCurPos++; 19 } 20 //如果前面p有过*，且前面的if都不满足，则将s往后挪到前面s匹配p的*的位置下标+1，并将p下标挪到*的下一个位置 21 else if(pStarPos != -1) { 22 pCurPos = pStarPos + 1; 23 sMatch++; 24 sCurPos = sMatch; 25 } 26 else { 27 return false; 28 } 29 } 30 //如果前面s和p已经匹配，但是p后面还有字符没和s匹配，则只能是*，才能正确匹配，否则无法匹配 31 while(pCurPos < p.length() && p.charAt(pCurPos) == '*') { 32 pCurPos++; 33 } 34 return pCurPos == p.length(); 35 }
法二（借鉴）：dp，dp[i, j]表示s前i个字符和p前j个字符是否匹配。代码如下（耗时104ms）：
1 //dp[i, j]表示s前i个字符串和p前j个字符串是否匹配 2 public boolean isMatch(String s, String p) { 3 boolean dp[][] = new boolean[s.length() + 1][p.length() + 1]; 4 dp[0][0] = true; 5 //初始化 6 for(int i = 1; i <= p.length(); i++) { 7 if(p.charAt(i - 1) == '*') { 8 dp[0][i] = dp[0][i - 1]; 9 } 10 } 11 //计算dp 12 for(int i = 1; i <= s.length(); i++) { 13 for(int j = 1; j <= p.length(); j++) { 14 if(p.charAt(j - 1) == '*') { 15 dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; 16 } 17 else { 18 dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && dp[i - 1][j - 1]; 19 } 20 } 21 } 22 return dp[s.length()][p.length()]; 23 }