题目
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).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “*”) → true
isMatch(“aa”, “a*”) → true
isMatch(“ab”, “?*”) → true
isMatch(“aab”, “c*a*b”) → false
分析
字符串匹配问题，有两种解决思路：
- 采用递归实现，但是性能不好，TLE；
- 贪心解决，参考网址
AC代码
class Solution {
public:
//字符串模式匹配问题，s为匹配串，p为模式串
bool isMatch(string s, string p) {
return isMatch1(s.c_str(), p.c_str());
}
/*方法一：采用贪心的性质 AC*/
bool isMatch1(const char *s, const char *p) {
//? match one
//* match 0,1,2,3..
// aaaabc *c true
const char* star = nullptr;
const char* rs = nullptr;
while (*s) {
if (*s == *p || *p == '?') { //match
s++; p++;
continue;
}
if (*p == '*') {
star = p; // record star
p++; //match from next p
rs = s; // record the position of s , star match 0
continue;
}
if (star != nullptr) { //if have star in front then backtrace
p = star + 1; //reset the position of p
s = rs + 1;
rs++; //star match 1,2,3,4,5....
continue;
}
return false; //if not match return false
}
while (*p == '*') p++; //skip continue star
return *p == ' '; // successful match
}
/*方法二：利用字符串指针递归解决 性能不好 TLE*/
bool isMatch2(const char *s, const char *p)
{
if (p == NULL || s == NULL)
return false;
else if (*p == ' ')
return (*s == ' ');
else
{
if (*p == '*')
{
while (*p == '*')
++p;
/*处理'*'可以匹配任意长度任意格式的字符串*/
while (*s != ' ')
{
if (isMatch2(s, p))
return true;
++s;
}//while
return isMatch2(s, p);
}
else if((*s!=' ' && *p == '?') || (*s == *p)){
return isMatch2(++s, ++p);
}//else
return false;
}//else
}
};