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
全匹配问题，也就是正则式的问题，题目要求两个字符串是否匹配，？代表任意一个字母，＊代表任意个字母，也可以是0个。
第一次写的时候出现了很多问题，我用了递归，但由于＊代表的是任意字母组合，因此也就比较麻烦，而第一次写出的代码，虽然在本地可以运行成功，但是提交的时候超时。代码如下：
public static boolean isMatch(String s, String p) {
char[] str1 = s.toCharArray();
char[] str2 = p.toCharArray();
int num = 0;
for( int i =0;i<p.length();i++){
if( str2[i] == '*')
num++;
}
num = s.length() - p.length() + num;
System.out.println( s.length()+" "+p.length()+" "+num);
return Match(str1,str2,0,0,num);
}
public static boolean Match(char[] str1,char[] str2,int a,int b,int num) {//num 表示＊可以代表的字符数
if ( num<0 )
return false;
int len1 = str1.length,len2 = str2.length;
if( a == len1 && b == len2)//两个数组都走到头了
return true;
if( a == len1 && str2[b] != '*')//只有第一个数组走到头了
return false;
else if ( a == len1 && str2[b] == '*'){
while( b < len2 && str2[b] == '*')
b++;
if( b == len2)
return true;
else
return false;
}
if( b == len2 ) //只有第二个数组走到头了
return false;
if( str1[a] == str2[b] || str2[b] == '?'){//遇到相同的字母或者？
while( a<len1 && b<len2 && str1[a] == str2[b]){
a++;
b++;
}
return Match(str1,str2,a++,b++,num);
}
if( str2[b] == '*'){ //遇到＊
while( b<len2 && str2[b] == '*') //连着的＊相当于一个＊
b++;
if( b == len2 )
return true;
for( int i = a,j = b,k = num;i<len1 ;){
k = num;
j = b;
while( i<len1 && j<len2 && str1[i] != str2[b]){ //寻找＊后匹配str[b]的字符
i++;
k--;
}
while( i<len1 && j<len2 && (str1[i] == str2[j] || str2[j] == '?' )){ //之后的字符也要匹配
i++;
j++;
}
if( k<0)
continue;
if( i<len1 && j<len2 && str1[i] != str2[j] && str2[j] != '*')//如果不匹配是因为字符不一样且不是？
continue;
else if( Match(str1,str2,i,j,k) )
return true;
}
}
return false;
}
然后发现了关键的一点： 1.当str1与str2分别到了i和j的时候。同时在str2[j]的位置遇到了＊（后面还有别的＊的情况下）。
2.之前的方法是，找str1[i]（包括str1[i]）之后遇到的所有的str2[j]之后的第一个字母a（非＊），然后再按照之前的规则进行匹配，遇到下一个＊的时候也会按照刚才的规则进行判断，一旦，错误，将回到第一个＊的地方重新进行判断。
3.这里就存在一个可以优化的点，就是在遇到下一个＊的时候，如果已经匹配成功，那么就算之后匹配失败，其实也不用重新返回第一个＊来进行判断，只需要回到当前的＊处接着判断就可以了，这样的话其实不用递归会比较好写一点。
代码如下：
public static boolean isMatch(String s, String p) {
int len1 = s.length(),len2 = p.length();
char[] str1 = s.toCharArray();
char[] str2 = p.toCharArray();
int i = 0, j = 0, pre = -1,before_i = -1,before_j = -1;
while( i < len1 ){
if( j < len2 && (str1[i] == str2[j] || str2[j] == '?')){
i++;
j++;
}
else if( j < len2 && str2[j] == '*'){
before_i = i;
before_j = j;
j++;
}else if( before_i != -1){
i = before_i;
j = before_j+1;
before_i++;
}else
return false;
}
while( j<len2 && str2[j] == '*')
j++;
if( j == len2 )
return true;
else
return false;
}
最后是基本接近最快。