044 Wildcard Matching
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 *.
解释下题目：
自己实现通配符。
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];
}
思路就是默认是匹配的，然后两个从最后开始匹配，简单说就是目前匹配与否，取决于之前是否匹配，如果匹配那么判断当前是否匹配，如果匹配则“继承”之前的状态，如果不匹配则直接false
