2023华为od机试C卷【掌握单词的个数】Python

2023华为od机试C卷【掌握单词的个数】

问题分析

1. 输入内容：

   • 具体的单词数量和单词列表。
   • 一个包含字母和 ? 的字符串，该字符串表示可以用来构词的字符。

2. 目标：

   • 计算哪些单词可以由给定字符以及 ?（作为通配符）构成。

解题思路

1. 字符统计：

   • 使用一个数组统计允许构成的字符（字母 a-z）的数量。
   • 统计 ? 的数量，作为可以灵活使用的字符。

2. 每个单词验证：

   • 对于每个单词，统计它的字母的数量。
   • 逐个比较该单词所需的字母数量与允许使用的字符数量。
     • 如果单词中某个字母的需求超过了可用字符，则计算缺口，并检查是否可以用 ? 来弥补这些缺口。

3. 计数合法单词：

   • 如果一个单词可以由给定字符及适量的 ? 构成，则将其计入可构成的单词总数。

4. 输出结果：

   • 最后输出可以被构成的单词数量。

实现步骤

1. 读取输入数据。
2. 统计可用字符和 ? 的数量。
3. 遍历每个单词并验证是否可以构成：
   • 使用临时计数器来处理 ? 的数量。
4. 输出满足条件的单词数量。

复杂度分析

• 这个方法的时间复杂度主要取决于单词的数量以及每个单词的长度，整体复杂度为 (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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

该真题和力扣拼写单词有点类似

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

1
2
3
4
5
6
7
8
9
10