P76011 剪贴字母 — 题解

专题： 字符串
适用题目： 新生 OJ 本地题包中的 P76011，不要直接用于外站同名题。

解题思路

用字符计数数组记录纸上的字母数量，再逐个消耗目标短句的字母。

复杂度

时间 $O(n+m)$，额外空间 $O(256)$。

易错点

空格不参与匹配，大小写要区分；目标所需数量不能超过库存。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    char a[1005], b[1005]; int count[256] = {0}, ok = 1;
    fgets(a,sizeof a,stdin); fgets(b,sizeof b,stdin);
    for (int i = 0; a[i]; i++) if (a[i]!=' ') count[(unsigned char)a[i]]++;
    for (int i = 0; b[i]; i++) if (b[i]!=' ' && b[i]!='\n') {
        if (--count[(unsigned char)b[i]] < 0) ok = 0;
    }
    puts(ok ? "YES" : "NO");
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a,b;
    getline(cin,a);
    getline(cin,b);
    map<char,int> f;
    for(char c:a)if(c!=' ')f[c]++;
    bool ok=true;
    for(char c:b)if(c!=' '){
        f[c]--;
        if(f[c]<0)ok=false;
    }
    cout<<(ok?"YES":"NO")<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。