生命不息,奋斗不止

题解 CF1023A 【Single Wildcard Pattern Matching】

2020-11-30 23:25:00


我的思路

我的思路就是将整个输入的 $s1$ 字符串与 $s2$ 进行比对。在此过程中,我们分别从开头到结尾各做一次循环,记录下是从什么时候开始不一样的。我们拿样例举例:

图中的红色框就是我们即将用来代替“ $*$ ”的。所以只要将红色框内的东西判断一下大小写就好了。

吹毛求疵

这道题有一个坑。首先样例中有过找不到“ $*$ ”号的情况,如果有这种情况我们这种算法是会出问题的。所以我们加一句话来判断这个是否合格:

if(s1.find('*') == s1.npos){ //如果找不到*号
    cout << "NO" << endl;
    return 0; //直接再见
}

贴代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n1, n2;//无脑输入
    cin >> n1 >> n2;
    string s1, s2;
    cin >> s1 >> s2;
    if(s1.find('*') == s1.npos){
        cout << "NO" << endl;
        return 0;
    }

    int fr;//寻找起点终点
    for(int i = 0; i < s1.size(); i++){
        if(s1[i] != s2[i]){
            fr = i;
            break;
        }
    }
    int bc;
    for(int i = s1.size()-1; i <=0; i--){
        if(s1[i] != s2[i]){
            bc = i;
            break;
        }
    }

    for(int i = fr; i <= bc; i++){
        if(!islower(s2[i])){ //判断是否小写
            cout << "NO" << endl;
            return 0; //有不是小写的先再见
        }
    }
    cout << "YES" << endl;
    return 0;
}