Description
Implement wildcard pattern matching with support for '?' and '*'.
Example
'?' 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
- 思路二：迭代回溯，两个指针
- is：指向s的下一次迭代的位置，初始为同p的'*'对应位置，然后以后的每一次迭代加1
- ip: 指向p的最近的一个'*'的位置
代码
- 递归超时。
bool isMatch(string s, string p) {
int slen = s.size(), plen = p.size();
string pattern;
int j = 0;
while (j < plen){
if (j > 0 && p[j] == '*' && p[j - 1] == p[j]){
j++;
continue;
}
pattern += p[j++];
}
return helper(s, slen, 0, pattern, pattern.size(), 0);
}
bool helper(string &s, int slen, int i, string &p, int plen, int j){
if (i == slen && j == plen) return true;
if (j == plen) return false;
if (i == slen) return p[j] == '*' ? helper(s, slen, i, p, plen, j + 1) : false;
if (s[i] == p[j] || p[j] == '?')
return helper(s, slen, i + 1, p, plen, j + 1);
else if (p[j] == '*'){
bool flag = false;
while (j + 1 < plen && p[j + 1] == p[j]) j++;
flag = helper(s, slen, i + 1, p, plen, j);
if (!flag && j + 1 < plen && (p[j + 1] == s[i] || p[j + 1] == '?'))
flag = helper(s, slen, i, p, plen, j + 1);
return flag;
}
else return false;
}- 迭代回溯
class Solution {
public:
bool isMatch(string s, string p) {
int slen = s.size(), plen = p.size();
int i = 0, j = 0, is = -1, ip = -1;
while(i < slen){
if(p[j] == '*'){
is = i;
ip = j++;
}
else{
if(s[i] == p[j] || p[j] == '?'){
i++;
j++;
}
else if(ip == -1) return false;
else {
i = ++is;
j = ip + 1;
}
}
}
while(j < plen && p[j] == '*') j++;
return j == plen;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
