题解 | #字符串通配符#

字符串通配符

https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036

递归的时间复杂度太大了，字符串稍微复杂且长度超过50就容易超时。我参考了C排名第一的代码（有bug：a* a##### 运行为true，且会匹配到最后，正确答案为false），并进行了优化。

思路：

用指针记录当前’*‘的位置与当前匹配字符的位置（开始时'*'的匹配数为0），按匹配规则继续向后匹配，当遇到不匹配情况时回溯到之前的’*‘的位置再匹配，此时'*'的匹配数+1。当遇到非字母、数字时该次’*‘匹配结束。

优化代码：

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool is(char c){
    if(isdigit(c) || islower(c)){
        return true;
    }
    return false;
}
bool match(char* s1,char* s2){
    int i=0,j=0,i_prev,j_prev,flag=0;
    while(s2[j]!='\0'){
        s1[i]=tolower(s1[i]);
        s2[j]=tolower(s2[j]);
        if(s1[i]=='*' && is(s2[j])){
            i_prev=i;//记录'*'的位置             
            j_prev=j;//记录当前匹配字符的位置             
            flag=1;
            i++;
        }
        else if(s1[i]=='*'){//如果当前通配符为'*'，且要匹配的字符串是符号就视该'*'匹配0个字符
            i++;
        }
        else if(s1[i]==s2[j] || (s1[i]=='?' && is(s2[j]))){
            i++;
            j++;
        }
        else if(flag){
            i=i_prev;
            j=j_prev+1;//'*'在匹配字符串的匹配数+1
            flag=0;//重置，当遇到最后通配符为'*'且匹配的字符串当前为符号的情况时提前退出循环
        }
        else{
            return false;
        }
    }
    while(s1[i]!='\0'){
        if(s1[i]!='*'){
            return false;
        }
        i++;
    }
    return true;
}
int main(){
    char s1[100],s2[100];
    while(cin >> s1 >> s2){
        cout << (match(s1,s2)?"true":"false");
    }
}

递归代码(可以通过所有用例)：

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool is(char c){
    if(isdigit(c) || islower(c)){
        return true;
    }
    return false;
}
bool match(char* s1,char* s2){
    *s1=tolower(*s1);
    *s2=tolower(*s2);
    if(*s1=='\0' && *s2=='\0'){
        return true;
    }
    else if(*s1=='\0'){
        return false;
    }
    else if(*s2=='\0'){
        while(*s1!='\0'){
            if(*s1!='*'){
                return false;
            }
            s1++;
        }
        return true;
    }
    if(*s1==*s2 || (*s1=='?' && is(*s2))){
       return match(s1+1,s2+1);
    }
    else if(*s1=='*'){
        while(*s1=='*'){
            s1++;
        }
        s1--;
        if(is(*s2)){
            return match(s1+1,s2+1) || match(s1,s2+1) || match(s1+1,s2);
        }
        else{
            return match(s1+1,s2);
        }
    }
    return false;
}
int main(){
    char s1[100],s2[100];
    while(cin >> s1 >> s2){
        cout << (match(s1,s2)?"true":"false");
    }
}