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).
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 = "*a*b" 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
AC code:
class Solution {
public:
bool isMatch(string s, string p) {
int sp = 0;
int pp = 0;
int match = 0;
int start = -1;
while (sp < s.length()) {
if (pp < p.length() && (s[sp] == p[pp] || p[pp] == ‘?‘)) {
sp++;
pp++;
} else if (pp < p.length() && p[pp] == ‘*‘) {
start = pp;
match = sp;
pp++;
} else if (start != -1) {
pp = start + 1;
match++;
sp = match;
} else return false;
}
while (pp < p.length() && p[pp] == ‘*‘) {
pp++;
}
return pp == p.length();
}
};
Runtime: 24 ms, faster than 88.38% of C++ online submissions for Wildcard Matching.
原文：https://www.cnblogs.com/ruruozhenhao/p/9800505.html