🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

单词大师(100分)

🌍 评测功能需要 订阅专栏 后私信联系清隆解锁～

🍓OJ题目截图

🥮 单词大师

问题描述

给定一个字符串数组 $words$ 和一个字符串 $chars$。如果可以用 $chars$ 中的字母拼写出 $words$ 中的某个单词，则认为你掌握了这个单词。$words$ 中的字符仅由小写字母 $a-z$ 和特殊字符 ? 组成，其中 ? 可以代表任意一个字母。

注意：拼写时，$chars$ 中的每个字母只能使用一次，? 也只能使用一次。

请输出你能够拼写出的 $words$ 中的单词数量。如果一个也拼写不出，则输出 $0$。

输入格式

第一行输入一个整数 $N$，表示数组 $words$ 的长度。

接下来 $N$ 行，每行输入一个字符串，表示 $words$ 中的一个单词。

最后一行输入一个字符串 $chars$。

其中，$1\le N\le 100$，$1\le word[i].length,chars.length\le 100$。

输出格式

输出一个整数，表示你能够拼写出的 $words$ 中的单词数量。

样例输入

4
cat
bt
hat
tree
atach??

样例输出

3

样例输入

3
hello
world
cloud
welldonehoneyr

样例输出

2

样例输入

3
apple
car
window
welldoneapplec?

样例输出

2

数据范围

• $1\le N\le 100$
• $1\le word[i].length,chars.length\le 100$

题解

这道题可以通过统计字符频率的方式来判断是否能拼写出每个单词。

1. 首先统计 $chars$ 中每个字母出现的次数，以及 ? 出现的次数。
2. 对于每个单词 $word$，统计其中每个字母出现的次数。
3. 遍历单词的每个字母，如果该字母在 $chars$ 中出现的次数大于等于在 $word$ 中出现的次数，则可以拼写；否则，如果 ? 的数量大于等于不足的字母数，也可以拼写；否则，无法拼写该单词。
4. 如果能拼写该单词，则答案加一。
5. 最后输出答案即可。

时间复杂度为 $O(NL)$，其中 $N$ 为单词数量，$L$ 为单词的平均长度。空间复杂度为 $O(1)$，因为只需要常数级的额外空间。

参考代码

• Python

n = int(input())
words = []
for _ in range(n):
    words.append(input())
chars = input()

def can_spell(word, chars):
    cnt_word = [0] * 26
    for c in word:
        cnt_word[ord(c) - ord('a')] += 1
    
    cnt_chars = [0] * 26
    wild = 0
    for c in chars:
        if c == '?':
            wild += 1
        else:
            cnt_chars[ord(c) - ord('a')] += 1
    
    for i in range(26):
        if cnt_word[i] > cnt_chars[i]:
            if wild >= cnt_word[i] - cnt_chars[i]:
                wild -= cnt_word[i] - cnt_chars[i]
            else:
                return False
    
    return True

ans = 0
for word in words:
    if can_spell(word, chars):
        ans += 1

print(ans)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] words = new String[n];
        for (int i = 0; i < n; i++) {
            words[i] = sc.next();
        }
        String chars = sc.next();
        
        int ans = 0;
        for (String word : words) {
            if (canSpell(word, chars)) {
                ans++;
            }
        }
        
        System.out.println(ans);
    }
    
    private static boolean canSpell(String word, String chars) {
        int[] cntWord = new int[26];
        for (char c : word.toCharArray()) {
            cntWord[c - 'a']++;
        }
        
        int[] cntChars = new int[26];
        int wild = 0;
        for (char c : chars.toCharArray()) {
            if (c == '?') {
                wild++;
            } else {
                cntChars[c - 'a']++;
            }
        }
        
        for (int i = 0; i < 26; i++) {
            if (cntWord[i] > cntChars[i]) {
                if (wild >= cntWord[i] - cntChars[i]) {
                    wild -= cntWord[i] - cntChars[i];
                } else {
                    return false;
                }
            }
        }
        
        return true;
    }
}

• Cpp

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

bool canSpell(string word, string chars) {
    vector<int> cntWord(26, 0);
    for (char c : word) {
        cntWord[c - 'a']++;
    }
    
    vector<int> cntChars(26, 0);
    int wild = 0;
    for (char c : chars) {
        if (c == '?') {
            wild++;
        } else {
            cntChars[c - 'a']++;
        }
    }
    
    for (int i = 0; i < 26; i++) {
        if (cntWord[i] > cntChars[i]) {
            if (wild >= cntWord[i] - cntChars[i]) {
                wild -= cntWord[i] - cntChars[i];
            } else {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }
    string chars;
    cin >> chars;
    
    int ans = 0;
    for (string word : words) {
        if (canSpell(word, chars)) {
            ans++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}