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
解题思路一：
参考之前写的Java for LeetCode 010 Regular Expression Matching，可以很轻松的用递归写出代码，JAVA实现如下：
static public boolean isMatch(String s, String p) {
if(s.length()==0){
for(int i=0;i<p.length();i++)
if(p.charAt(i)!='*')
return false;
return true;
}
if (p.length() == 0)
return s.length() == 0;
else if (p.length() == 1)
return p.charAt(0)=='*'||(s.length() == 1&& (p.charAt(0) == '?' || s.charAt(0) == p.charAt(0)));
if(p.charAt(0)!='*'){
if(p.charAt(0)!=s.charAt(0)&&p.charAt(0)!='?')
return false;
return isMatch(s.substring(1),p.substring(1));
}
int index=0;
while(index<p.length()){
if(p.charAt(index)=='*')
index++;
else break;
}
if(index==p.length())
return true;
p=p.substring(index);
for(int i=0;i<s.length();i++){
if(isMatch(s.substring(i),p))
return true;
}
return false;
}
结果Time Limit Exceeded！也就是说这种类似暴力枚举的算法肯定不能通过！
解题思路二：
用两个指针indexS和indexP遍历s和p，同时用两个指针starIndex和sPosition来记录*遍历过程中*最后一次出现的位置和对应的indexP的位置，一旦s和p不匹配，就回到starIndex的位置，同时sPosition+1，接着遍历，直到遍历完整个s为止，注意边界条件，JAVA实现如下：
static public boolean isMatch(String s, String p) {
int indexS=0,indexP=0,starIndex=-2,sPosition=-2;
while(indexS<s.length()){
if(starIndex==p.length()-1)
return true;
if(indexP>=p.length()){
if(starIndex<0)
return false;
indexP=starIndex+1;
indexS=++sPosition;
}
if(s.charAt(indexS)==p.charAt(indexP)||p.charAt(indexP)=='?'){
indexS++;
indexP++;
}
else if(p.charAt(indexP)=='*'){
starIndex=indexP++;
sPosition=indexS;
}
else if(starIndex>=0){
indexP=starIndex+1;
indexS=++sPosition;
}
else return false;
}
while(indexP<p.length()){
if(p.charAt(indexP)!='*')
return false;
indexP++;
}
return true;
}