牛客- 字符串通配符
问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等地方。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
：匹配0个或以上的字符（注：能被和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符
注意：匹配时不区分大小写。
输入：
通配符表达式；
一组字符串。
输出：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度：1≤s≤100
进阶：时间复杂度：O(n2) ，空间复杂度：O(n)
输入描述:
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
输出描述:
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
示例1
输入
te?t*.*
txt12.xls
输出
false
利用递归：分几种情况
利用index1和index2分别标识当前遍历到的字符串1和字符串2
其中字符串1是含通配符的
-
如果都是字母，并且是同一个字母（不区分大小写），index1和index2都向后走
-
如果不是字母，但是也是相同的，比如都是# . 之类的 index1和index2都向后走
-
如果通配符遇到 ？，那么可以匹配一个数字字符或者字母字符，但是如果str此时不是字母或数字，不能匹配，返回false。如果满足那么index1和index2都向后走
-
如果遇到
*，注意，因为多个*的作用是一样的，所以首先要找到最后一个*。如果str不是字母或数字，返回false。如果是，分几种情况-
*匹配0个字符，即 把*看成不存在，跳过： index1向后走，index2不动
-
*匹配1个字符，即 index1和index2同时向后走一步
-
*匹配多个字符，即该*能抵消多个字符串的字符，让index1不动，index2向后走。递归看下一次的情况
-
-
其他情况就是false了
#include<iostream>
using namespace std;bool ismatch(string& tokens,int index1,string& str,int index2){//同时结束if(index1==tokens.size() && index2==str.size()){return true;}//一个结束了 一个没结束，说明不匹配 返回falseif(index1==tokens.size() || index2==str.size()){return false;}//如果都是字母 并且俩相等，就递归两个字符串的下一个位置if(isalpha(tokens[index1]) && isalpha(str[index2]) && toupper(tokens[index1]) == toupper(str[index2])){return ismatch(tokens,index1+1,str,index2+1);}//如果不是字母且相等 如都是 . 或者 #if(tokens[index1] == str[index2]){return ismatch(tokens,index1+1,str,index2+1);}//如果tokens为 ?if(tokens[index1]=='?'){//如果不是if(!isdigit(str[index2]) && !isalpha(str[index2])){return false;}return ismatch(tokens,index1+1,str,index2+1);}//如果tokens是*//因为多个连着的* 和 一个*的效果是一样的，所以要找到最后一个*if(tokens[index1] =='*'){//找最后一个*while(index1 < tokens.size()-1 && tokens[index1+1] =='*'){++index1;}//如果 str是非字母或者数字，就无法匹配if(!isdigit(str[index2]) && !isalpha(str[index2])){return false;}//然后*可以匹配1个，可以匹配0个 可以匹配多个//匹配0个就是 str不走，tokens走//匹配1个就是，str和tokens都走一步//匹配多个，就是str走，tokens不走 ,即继续下一次匹配return ismatch(tokens,index1+1,str,index2)|| ismatch(tokens,index1+1,str,index2+1)|| ismatch(tokens,index1,str,index2+1);}return false;}
int main(){string tokens;string str;cin >> tokens >> str;if(ismatch(tokens,0, str,0)){cout << "true" <<endl;}else{cout <<"false" <<endl;}return 0;
}