Given an input string (
s) and a pattern (p), implement wildcard pattern matching with support for'?'and'*'.
'?'Matches any single character.
'*'Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example：
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Input:
s = "aa"
p = "*"
Output: true
Explanation: ' * ' matches any sequence.
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Input:
s = "adceb"
p = "ab"
Output: true
Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce".
Input:
s = "acdcb"
p = "a*c?b"
Output: false
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 *.
解釋下題目：
自己實現(xiàn)通配符翘县。
1. 二維矩陣判斷法骑歹，從這里借鑒的
實際耗時：59ms
public boolean isMatch(String s, String p) {
boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
match[s.length()][p.length()] = true;
for (int i = p.length() - 1; i >= 0; i--) {
if (p.charAt(i) != '*')
break;
else
match[s.length()][i] = true;
}
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = p.length() - 1; j >= 0; j--) {
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')
match[i][j] = match[i + 1][j + 1];
else if (p.charAt(j) == '*')
match[i][j] = match[i + 1][j] || match[i][j + 1];
else
match[i][j] = false;
}
}
return match[0][0];
}
??思路就是默認是匹配的，然后兩個從最后開始匹配首装，簡單說就是目前匹配與否瘪阁，取決于之前是否匹配，如果匹配那么判斷當(dāng)前是否匹配，如果匹配則“繼承”之前的狀態(tài)，如果不匹配則直接false
