假设某一单词word和字符串chars对应的计数器分别为cnt_word和cnt_chars，问号字符?出现的次数为num。那么在逐一比较word中字符出现次数和chars中元素出现字符时，若出现cnt_word[k] > cnt_chars[k]，则可以使用cnt_word[k] - cnt_chars[k]个?来作为万能字符。若发现此时?出现的次数为num已经小于cnt_word[k] - cnt_chars[k]，则无法拼凑出单词word。

代码

Python

# 题目：【哈希表】2023C-掌握单词个数
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：哈希表
# 代码看不懂的地方，请直接在群上提问


# 检查cnt_chars能否完全拼写出cnt_word的函数
# 其中num为cnt_chars中问号字符的个数
def check(cnt_chars, cnt_word, num):
    # 遍历cnt_word中的所有键k
    for k in cnt_word.keys():
        # 如果chars中k出现的个数大于等于word
        # 则可以直接使用这些字符k来拼写出word中的k
        if cnt_chars[k] >= cnt_word[k]:
            continue
        # 如果chars中k出现的个数小于word
        else:
            # 则需要使用cnt_word[k] - cnt_chars[k]个万能字符
            # 才能使得字符k能够被在chars中被全部拼写
            num -= cnt_word[k] - cnt_chars[k]
            # 若使用完之后，num的个数小于0，则说明万能字符的个数不足
            # 不可能完成拼写
            # 直接返回False
            if num < 0:
                return False
    # 如果能够顺利退出上述循环，即通过了检查，返回True
    return True


from collections import Counter

# 输入words的个数
n = int(input())
words = list()
# 循环n次，输入n个单词
for _ in range(n):
    words.append(input())

# 输入chars字符串
chars = input()

# 获得chars字符串对应的元素频率哈希表
cnt_chars = Counter(chars)

ans = 0
# 获得chars中问号字符的个数
num = cnt_chars["?"]

# 遍历words中的每一个单词word
for word in words:
    # 构建word对应的哈希表计数器
    cnt_word = Counter(word)
    # 调用check函数，将结果加入ans中
    ans += int(check(cnt_chars, cnt_word, num))


print(ans)

Java

import java.util.*;

public class Main {
    static boolean check(HashMap<Character, Integer> cntChars, HashMap<Character, Integer> cntWord, int num) {
        for (char k : cntWord.keySet()) {
            if (cntChars.getOrDefault(k, 0) >= cntWord.getOrDefault(k, 0)) {
                continue;
            } else {
                num -= cntWord.getOrDefault(k, 0) - cntChars.getOrDefault(k, 0);
                if (num < 0) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        List<String> words = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            words.add(scanner.nextLine());
        }

        String chars = scanner.nextLine();
        HashMap<Character, Integer> cntChars = new HashMap<>();
        for (char c : chars.toCharArray()) {
            cntChars.put(c, cntChars.getOrDefault(c, 0) + 1);
        }

        int ans = 0;
        int num = cntChars.getOrDefault('?', 0);

        for (String word : words) {
            HashMap<Character, Integer> cntWord = new HashMap<>();
            for (char c : word.toCharArray()) {
                cntWord.put(c, cntWord.getOrDefault(c, 0) + 1);
            }
            ans += check(cntChars, cntWord, num) ? 1 : 0;
        }

        System.out.println(ans);
    }
}

C++

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

bool check(unordered_map<char, int>& cntChars, unordered_map<char, int>& cntWord, int num) {
    for (auto& kv : cntWord) {
        char k = kv.first;
        if (cntChars[k] >= cntWord[k]) {
            continue;
        } else {
            num -= cntWord[k] - cntChars[k];
            if (num < 0) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    cin.ignore(); // To consume the newline character

    vector<string> words(n);
    for (int i = 0; i < n; ++i) {
        cin >> words[i];
    }
    cin.ignore(); // To consume the newline character

    string chars;
    getline(cin, chars);

    unordered_map<char, int> cntChars;
    for (char c : chars) {
        cntChars[c]++;
    }

    int ans = 0;
    int num = cntChars['?'];

    for (string& word : words) {
        unordered_map<char, int> cntWord;
        for (char c : word) {
            cntWord[c]++;
        }
        ans += check(cntChars, cntWord, num) ? 1 : 0;
    }

    cout << ans << endl;
    return 0;
}

时空复杂度

时间复杂度：O(NM)。其中M为每一个单词word的字符种类个数，最高为26。单次调用check()函数的时间复杂度为O(M)。

空间复杂度：O(N)。