网站建设公司介绍网站建设奕网情深

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

✨ 本系列打算持续跟新华为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] * 26for c in word:cnt_word[ord(c) - ord('a')] += 1cnt_chars = [0] * 26wild = 0for c in chars:if c == '?':wild += 1else:cnt_chars[ord(c) - ord('a')] += 1for 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 Falsereturn Trueans = 0
for word in words:if can_spell(word, chars):ans += 1print(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;
}