Wildcard Matching
描述
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
分析
跟上一题很类似。
主要是'*'的匹配问题。p每遇到一个'*'，就保留住当前'*'的坐标和s的坐标，然后s从前往后扫描，如果不成功，则s++，重新扫描。
递归版
// Wildcard Matching
// 递归版，会超时，用于帮助理解题意
// 时间复杂度O(n!*m!)，空间复杂度O(n)
class Solution {
public:
bool isMatch(const string& s, const string& p) {
return isMatch(s.c_str(), p.c_str());
}
private:
bool isMatch(const char *s, const char *p) {
if (*p == '\0' || *s == '\0') return *p == *s;
else if (*p == '*') {
while (*p == '*') ++p; //skip continuous '*'
if (*p == '\0') return true;
while (*s != '\0' && !isMatch(s, p)) ++s;
return *s != '\0';
}
else if (*p == *s || *p == '?') return isMatch(++s, ++p);
else return false;
}
};迭代版
// Wildcard Matching
// 迭代版，时间复杂度O(n*m)，空间复杂度O(1)
class Solution {
public:
bool isMatch(const string& s, const string& p) {
return isMatch(s.c_str(), p.c_str());
}
private:
bool isMatch(const char *s, const char *p) {
bool star = false;
const char *str, *ptr;
for (str = s, ptr = p; *str != '\0'; str++, ptr++) {
switch (*ptr) {
case '?':
break;
case '*':
star = true;
s = str, p = ptr;
while (*p == '*') p++; //skip continuous '*'
if (*p == '\0') return true;
str = s - 1;
ptr = p - 1;
break;
default:
if (*str != *ptr) {
// 如果前面没有'*'，则匹配不成功
if (!star) return false;
s++;
str = s - 1;
ptr = p - 1;
}
}
}
while (*ptr == '*') ptr++;
return (*ptr == '\0');
}
};