题解 | #字符串通配符#

#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
/*统一大小写用transform
情况挺多，先在草稿搞清楚，再针对每种情况设计出对应的对策.不要合并太乱了
主要操作的2字符串的指针1j和2i，为了避免混乱就不要循环自加
同时函数judge判断结果，主函数再输出。
另外有可能有多种匹配情况，可能只有其中一种匹配上，所以当某一种匹配不上时，
需要继续尝试其他（记录所有可能新情况点，vector动态数组压入，尝试时出栈），
直到全部尝试都错才可以判错（vector为空）。尝试用递归调用judge，指针i\j可调，参数           
*/

//函数judge判断，2字符串指针j,i参数传入，默认0 0
bool judge(string s1, string s2,int i0=0,int j0=0) {
    int j = j0, i = i0;    //2字符串指针初始化
    vector<int>posi, posj;    //记录分叉点，用于回溯
    for (; j < s1.size() && i < s2.size();) {    //遍历2字符串进行匹配
        if (s1[j] == '?') {    //匹配1字符符
            if (isalnum(s2[i])) {  //字符合法继续检查
                i++, j++;
            } else {
                return false;    //非法字符返回错
            }
        } else if (s1[j] == '*') {    //匹配不定长字符
            if (s1[j + 1] == '*') {    
                //连续**时，可以当做1个'*'
                j++;    //**情况
            } else if (s1[j+1]=='?') {    
                //连续*?时，先匹配单字符该'?'为'*'
                j++;    //*?情况
                if(isalnum(s2[i]))
                    i++;
                else
                    return false;    //特殊字符报错
                s1[j]='*';
            }else if (s1[j + 1] == s2[i]) { //记录地点
                //匹配成功，将此时状态记录下来便于回溯
                posi.push_back(i); 
                posj.push_back(j);
                i++;
                j += 2; //找到下一对应字符，指针下移动
            } else {    //还未找到匹配的i指针，i指针下移继续匹配
                if (isalnum(s2[i])) {
                    i++;    //当前字符串2字符合法，下移指针继续找对应
                } else {
                    return false;    //非法字符
                }
            }
        } else {   //确定字符
            if (s1[j++] != s2[i++]) {    //字符不匹配，回溯更换匹配方式
                if (!posi.empty()) {  //回溯
                    i = posi.back() + 1;
                    posi.pop_back();    //销毁该记录
                    j = posj.back();
                    posj.pop_back();
                } else{    //用于回溯的记录为空，证明已无情况可回溯，已遍历全部匹配情况了，不匹配
                    return false;    //匹配失败
                }
            }
        }
    }
    if (i == s2.size() && (j == s1.size() || s1[s1.size() - 1] == '*' &&j == s1.size() - 1)) {
        return true;    //结束字符串遍历看是否2字符串都遍历完或特殊情况
    } else if (!posi.empty()) {  //否则有误，需要回溯。若无回溯说明错误
        i = posi.back() + 1;
        posi.pop_back();
        j = posj.back();
        posj.pop_back();
        return judge(s1, s2,i,j);
    }else
        return false;
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    //不区分大小写，需要统一
    transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
    transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
    if (judge(s1, s2)) {
        cout << "true";
    } else {
        cout << "false";
    }
    return 0;
}