题解 | #字符串通配符#
字符串通配符
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");
}
}
查看15道真题和解析
左边刷题右边 chat 效果很好
腾讯成长空间 6071人发布