题解 | #字符串通配符#

双指针，贪心+回溯。时间复杂度O(nm)，空间复杂度O(1)

#include <bits/stdc++.h>

using namespace std;

bool isnum(char s)  {
    if( s>= '0' && s<='9') {
        return true;
    }
    return false;
}

bool isword(char s) {
    if( s>= 'a' && s<= 'z') {
        return true;
    }
    if( s>= 'A' && s<= 'Z') {
        return true;
    }
    return false;
}

int main() {
    string p;
    cin>>p;
    string s;
    cin>>s;
    int sl = s.length();
    int pl = p.length();
    //双指针移动两个元素
    int i = 0, j = 0;
    //记录匹配到'*'的位置，方便操作
    int marks = -1, markp = -1;
    transform (s.begin(), s.end(), s.begin(), ::toupper);
    transform (p.begin(), p.end(), p.begin(), ::toupper);
    while (i < sl) { 
        if (j != pl && (s[i] == p[j] || (p[j] == '?' && ( isnum(s[i]) || isword(s[i]) )  )  )) {
          //直接字符匹配或者p里面是'?'，直接走
            i++;
            j++;
        }
        else if (j != pl && p[j] == '*') {
          //是'*'时，记录当前i和j,并且先把j指针走一步
            marks = i;
            markp = j;
            j++;
        }
        else if (markp != -1 && ( isnum(s[marks]) || isword(s[marks]) ) ) {
          //j走一步后和i不匹配，则需要用'*'匹配掉当前i。i往前走一步，j回到mark点的下一个位置，再继续比较
            i = marks + 1;
            j = markp + 1;
            marks++;
        }
        else {
          //没有完全匹配或者匹配不正确
            cout<<"false"<<endl;
            return 0;
        }
    }
    while (j < pl) {
      //s已经完全匹配完，但是j指针还没有走完的情况
        if (p[j] == '*') 
            j++ ;
        else{
            cout<<"false"<<endl;
            return 0;
        }
    }
    cout<<"true"<<endl;
    return 0;
}