HJ71 字符串通配符

题目描述

问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符

注意：匹配时不区分大小写。
 

输入：
通配符表达式；
一组字符串。

输出：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度：1/le s/le 100/1≤s≤100 
进阶：时间复杂度：O(n^2)/O(n2) ，空间复杂度：O(n)/O(n) 

输入描述：

先输入一个带有通配符的字符串，再输入一个需要匹配的字符串

输出描述：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

示例

输入：
te?t*.*
txt12.xls
输出：
false
输入：
**Z
0QZz
输出：
true

解题思路

代码如下：

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

bool check(string reg,string str){
    if(reg.length() == 0 && str.length() == 0)return true;
    if(reg.length() == 0 || str.length() == 0)return false;
    
    if(reg[0] == '?'){
        if(!isdigit(str[0]) && !isalpha(str[0]) )return false;
        return check(reg.substr(1,reg.length()-1), str.substr(1,str.length()-1));
    }else if(reg[0] == '*'){
        int tmp = 0;
        while(reg[tmp] == '*'){
            tmp++;
        }
        tmp--;
        return check(reg.substr(tmp+1,reg.length()-tmp),str) || check(reg.substr(tmp+1,reg.length()-tmp),str.substr(1,str.length()-1)) || check(reg.substr(tmp,reg.length()-tmp+1),str.substr(1,str.length()-1));
    }else if(tolower(reg[0]) == tolower(str[0])){
        return check(reg.substr(1,reg.length()-1),str.substr(1,str.length()-1));
    }
    return false;
}

int main(){
    string reg,str;
    while(cin>>reg>>str){
        if(check(reg,str))
            cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }
}