题目描述
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
给定字符串s和p，实现通配符匹配
'?' Matches any single character.
'' Matches any sequence of characters (including the empty sequence).
?匹配任意单个字符，匹配任何字符串（包括空串）
The matching should cover the entire input string (not partial).
Note:
- s could be empty and contains only lowercase letters a-z.
- p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "ab"
Output: true
Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
思路分析
动态规划的思想，用数组matches记录下来s的前i位于p的前j位的匹配情况。
例如，遍历到matches[3]记录字符串adceb的前3位（adc）与当前pattern(*a)是否匹配，因为在计算matches[4]会用到这个结果。
- 如果当前遍历的p的位置不是
*（含?），则正常的与s的第4位进行比较，然后与res[3]进行与操作（正常，前面如果都没匹配成功，就直接匹配失败了）； - 如果当前遍历的p的位置是
*，则从前往后找T，只要有T，后面就 - 都是T（也就是说只要前面的匹配成功了，后面接个通配符*，那后面就什么都可以匹配了，所以如果matches[3]是T，后面matches[4] matches[5] matches[6]管它多少都无所谓，都是T）
这里其实本来要用二维数组表示s[i]与p[j]的匹配结果的，但是由于递推公式，后面的只依赖于前一个，所以改为了一维的，p每遍历一位，这个一维数组就整个更新一遍。
代码实现
/**
* 1808 / 1808 test cases passed.
* Status: Accepted
* Runtime: 80 ms
*
* @param s
* @param p
* @return
*/
public boolean isMatch(String s, String p) {
if (p.length() == 0) {
return s.length() == 0;
}
boolean[] matches = new boolean[s.length() + 1];
matches[0] = true;
// 外层遍历pattern，内层遍历s
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) != '*') {
// 这里要从后往前遍历，是为了不受前面改动的影响
// 如果从前面遍历，res[i]可能被改动，这样res[i + 1]的结果会受res[i]改动的影响
// 例如本来匹配*a,是在*匹配的结果基础上，加上a，如果从前开始遍历，就会导致在*a的基础上遍历，成为匹配*aa了
for (int i = s.length() - 1; i >= 0; i--) {
matches[i + 1] = matches[i] && (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j));
}
} else {
int i = 0;
while (i <= s.length() && !matches[i]) {
i++;
}
for (; i <= s.length(); i++) {
matches[i] = true;
}
}
// 如果p的当前位不是*，那么就不可能和空串匹配了，所以matches[0]就永远是F
matches[0] = matches[0] && p.charAt(j) == '*';
}
return matches[s.length()];
}
