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
Since '*' matches any sequence of characters, we need to check every possibility within string s. Instead of using recursion, we can use iteration with two variables recording position of last '*' in pattern string and corresponding position in string s.
C++ Code:
/*
* func: wildcard_match
* goal: wildcard pattern match with support for '?' and '*'
* @param s: string to be checked
* @param p: pattern to be used
* return: true or false
*/
bool wildcard_match(const char* s, const char* p){
if(! *s && ! *p){
return true;
}
char* start_s = nullptr;
char* start_p = nullptr;
while(*s != '\0'){
if(*p == *s || *p == '?'){
++p;
++s;
}else if(*p == '*'){
//skip continuous '*'
while(*p == '*'){
++p;
}
//If '*' is the last letter, return true
if(*p == '\0'){
return true;
}
start_p = const_cast<char*>(p);
start_s = const_cast<char*>(s);
}else if((*p != '\0' || *p != *s) && start_p != nullptr){
//If current char is not matched, include it to the * and backtrace
s = ++start_s;
p = start_p;
}else{
return false;
}
}
//Check if remaining part of pattern is all of '*'
while(*p != '\0'){
if(*p++ != '*'){
return false;
}
}
return true;
}
Python Code:
# func: wildcard pattern match with support for '?' and '*'
# @param s: an input string
# @param p: a pattern string
# @return: True or False
def wildcard_match(s, p):
s_index = 0
p_index = 0
star = -1
while s_index < len(s) and p_index <= len(p):
if p_index != len(p):
if p[p_index] == '?' or p[p_index] == s[s_index]:
s_index += 1
p_index += 1
continue
if p[p_index] == '*':
star = p_index
p_index += 1
#Record the current index of s when a '*' occur in p
s_star = s_index
continue
if star != -1:
p_index = star + 1
s_index = s_star + 1
s_star += 1
continue
return False
#Remove '*' in the remaining part
while p_index < len(p) and p[p_index] == '*':
p_index += 1
if p_index == len(p):
if s_index == len(s):
return True
else:
return False
else:
return False
Reference Link:
[closed] Wildcard Matching - LeetCode http://discuss.leetcode.com/questions/222/wildcard-matching
