阅读量:0
2023华为od机试C卷【掌握单词的个数】
问题分析
输入内容：
- 具体的单词数量和单词列表。
- 一个包含字母和
?的字符串，该字符串表示可以用来构词的字符。
目标：
- 计算哪些单词可以由给定字符以及
?（作为通配符）构成。
- 计算哪些单词可以由给定字符以及
解题思路
字符统计：
- 使用一个数组统计允许构成的字符（字母 a-z）的数量。
- 统计
?的数量，作为可以灵活使用的字符。
每个单词验证：
- 对于每个单词，统计它的字母的数量。
- 逐个比较该单词所需的字母数量与允许使用的字符数量。
- 如果单词中某个字母的需求超过了可用字符，则计算缺口，并检查是否可以用
?来弥补这些缺口。
- 如果单词中某个字母的需求超过了可用字符，则计算缺口，并检查是否可以用
计数合法单词：
- 如果一个单词可以由给定字符及适量的
?构成，则将其计入可构成的单词总数。
- 如果一个单词可以由给定字符及适量的
输出结果：
- 最后输出可以被构成的单词数量。
实现步骤
- 读取输入数据。
- 统计可用字符和
?的数量。 - 遍历每个单词并验证是否可以构成：
- 使用临时计数器来处理
?的数量。
- 使用临时计数器来处理
- 输出满足条件的单词数量。
复杂度分析
- 这个方法的时间复杂度主要取决于单词的数量以及每个单词的长度，整体复杂度为 (O(n \times m))，其中 (n) 是单词的数量，(m) 是单词的平均长度。由于字符集限制在低容量（只针对
a-z），因此字符计数部分的操作是常数时间的。
这样的思路清晰地将问题分解为多个步骤，有助于系统地解决问题并保证实现的简洁和高效。
def main(): #这是程序的入口点，负责读取输入、处理数据并输出结果。 n = int(input()) #读取单词数量：首先读取一个整数 n，表示接下来将输入的单词的数量 words = [input().strip() for _ in range(n)] #读取单词：使用列表推导式读取 n 个单词。input().strip() 确保去掉每个单词前后的空格。 chars = input().strip() #读取一行字符串 chars，这其中可能包含字母和特殊字符 ?。 # Create a count map for the characters char_count_map = [0] * 26 magic_char_count = 0 # 初始化字符计数器：创建一个大小为 26 的列表 char_count_map # 用于统计每个字母出现的次数（对应于字母 a-z）。同时初始化一个变量 magic_char_count 用于统计 ? 字符的数量。 for char in chars: if char == '?': magic_char_count += 1 else: char_count_map[ord(char) - ord('a')] += 1 # 统计字符：遍历 chars 中的每个字符。如果是 ?，则增加 magic_char_count； # 否则，通过 ord 函数将字符转为对应的索引并更新 char_count_map 中的计数。 output_count = 0 #初始化输出计数：准备一个变量 output_count 用于记录可以用已给字符构成的合法单词的数量。 for word in words: #遍历每个单词：对于每一个输入的单词，接下来的计数和验证过程。 # Create a count map for the current word word_count_map = [0] * 26 for char in word: word_count_map[ord(char) - ord('a')] += 1 #统计单词字符：同样的，创建一个 word_count_map 来记录当前单词中每个字母的出现次数。 # Check if the word can be formed using the char_count_map and magic characters flag = True temp_count = magic_char_count #初始化标记及临时计数器：设置一个布尔变量 flag，用于判断当前单词是否可以被构成， #temp_count 初始化为 magic_char_count，用于在后续计算中追踪可以使用的魔法字符（即 ? 的数量）。 for k in range(26): if word_count_map[k] > char_count_map[k]: temp_count -= (word_count_map[k] - char_count_map[k]) if temp_count < 0: flag = False break #验证单词构成：遍历每个字母（从 a 到 z）。如果当前单词中某个字母的需求量超过了可用字符的数量， #则计算需要的大于之数，并从 temp_count 中减去。如果 temp_count 别减到负数，说明无法匹配该单词， #设置 flag 为 False 并跳出循环。 if flag: output_count += 1 #记录合法单词：如果 flag 为 True，说明当前单词可以由给定的字符及魔法字符构成，则将 output_count 增加 1。 print(output_count) if __name__ == "__main__": main() 该真题和力扣拼写单词有点类似
class Solution: def countCharacters(self, words: List[str], chars: str) -> int: ans = 0 cnt = collections.Counter(chars) for w in words: c = collections.Counter(w) if all([c[i] <= cnt[i] for i in c]): ans += len(w) return ans 