最新华为OD机试真题-单词大师(100分)

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

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

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

📎在线评测链接

=> 单词大师(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🥮 单词大师

问题描述

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

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

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

输入格式

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

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

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

其中，，。

输出格式

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

样例输入

4
cat
bt
hat
tree
atach??

样例输出

3

样例输入

3
hello
world
cloud
welldonehoneyr

样例输出

2

样例输入

3
apple
car
window
welldoneapplec?

样例输出

2

数据范围

题解

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

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

时间复杂度为 ，其中 为单词数量， 为单词的平均长度。空间复杂度为 ，因为只需要常数级的额外空间。

参考代码

• 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