当前位置：首页 > news >正文

华为OD机试 - 掌握单词个数（Python/JS/C/C++ 2024 D卷 100分）

news 2025/7/14 13:26:50

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有一个字符串数组 words 和一个字符串 chars 。

假如可以用 chars 中的字母拼写出 words 中的某个“单词”（字符串），那么我们就认为你掌握了这个单词。

words 的字符仅由 a-z 英文小写字母组成，例如 “abc” chars 由 a-z 英文小写字母和 “?” 组成。其中英文问号 “?” 表示万能字符，能够在拼写时当做任意一个英文字母。例如：“?” 可以当做 “a” 等字母。

注意：每次拼写时，chars 中的每个字母和万能字符都只能使用一次。

输出词汇表 words 中你掌握的所有单词的个数。没有掌握任何单词，则输出 0。

二、输入描述

第 1 行输入数组 words 的个数，记为 N。从第 2 行开始到第 N+1 行一次输入数组 words 的每个字符串元素。第 N+2 行输入字符串 chars。

三、输出描述

输出一个整数，表示词汇表 words 中你掌握的单词个数。

四、测试用例

1、输入

4
cat
bt
hat
tree
atach

2、输出

3、说明

atach可以拼写出单词cat和hat，因此掌握的单词是2个。

4、输入

4
cat
bt
hat
tree
at?ch

5、输出

6、说明

at?ch可以拼写出单词cat、hat和bt，因此掌握的单词是3个。

五、解题思路

要解决这个问题，我们需要以下几个步骤：

读取输入：
- 首先读取单词数组 words 的个数 N。
- 读取 N 个单词并存储在 words 列表中。
- 读取包含可用字符的字符串 chars。
统计字符频率：
- 统计 chars 中每个字符（包括万能字符 ?）的频率。
验证单词是否可拼写：
- 对于每个单词，检查其每个字符是否可以由 chars 中的字符构成，考虑万能字符 ?。
- 使用一个字典来记录 chars 中字符的剩余使用次数，在验证过程中逐个减少字符的可用次数。
计算掌握的单词个数：
- 如果一个单词可以被拼写出来，则增加掌握的单词计数。

六、Python算法源码

def count_mastered_words(words, chars):# 统计 chars 中每个字符的频率char_count = {}for ch in chars:char_count[ch] = char_count.get(ch, 0) + 1mastered_words_count = 0# 验证每个单词是否可以由 chars 中的字符拼写出来for word in words:if can_spell(word, char_count.copy()):mastered_words_count += 1return mastered_words_countdef can_spell(word, char_count):wildcard_count = char_count.get('?', 0)for ch in word:if char_count.get(ch, 0) > 0:char_count[ch] -= 1elif wildcard_count > 0:wildcard_count -= 1else:return Falsereturn Truedef main():# 读取单词的数量n = int(input())# 读取所有单词words = []for _ in range(n):words.append(input().strip())# 读取可用字符的字符串chars = input().strip()# 输出掌握的单词个数print(count_mastered_words(words, chars))if __name__ == "__main__":main()

七、JavaScript算法源码

function countMasteredWords(words, chars) {// 统计 chars 中每个字符的频率const charCount = {};for (const ch of chars) {charCount[ch] = (charCount[ch] || 0) + 1;}let masteredWordsCount = 0;// 验证每个单词是否可以由 chars 中的字符拼写出来for (const word of words) {if (canSpell(word, { ...charCount })) {masteredWordsCount++;}}return masteredWordsCount;
}function canSpell(word, charCount) {let wildcardCount = charCount['?'] || 0;for (const ch of word) {if (charCount[ch] && charCount[ch] > 0) {charCount[ch]--;} else if (wildcardCount > 0) {wildcardCount--;} else {return false;}}return true;
}function main() {// 读取单词的数量const n = parseInt(prompt("Enter number of words:"));// 读取所有单词const words = [];for (let i = 0; i < n; i++) {words.push(prompt("Enter a word:").trim());}// 读取可用字符的字符串const chars = prompt("Enter available characters:").trim();// 输出掌握的单词个数console.log(countMasteredWords(words, chars));
}// 调用 main 函数
main();

八、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>#define MAX_CHAR_COUNT 256int countMasteredWords(char words[][100], int n, char* chars) {int charCount[MAX_CHAR_COUNT] = {0};// 统计 chars 中每个字符的频率for (int i = 0; chars[i] != '\0'; i++) {charCount[(int)chars[i]]++;}int masteredWordsCount = 0;// 验证每个单词是否可以由 chars 中的字符拼写出来for (int i = 0; i < n; i++) {int tempCharCount[MAX_CHAR_COUNT];memcpy(tempCharCount, charCount, sizeof(charCount));if (canSpell(words[i], tempCharCount)) {masteredWordsCount++;}}return masteredWordsCount;
}bool canSpell(char* word, int* charCount) {int wildcardCount = charCount['?'];for (int i = 0; word[i] != '\0'; i++) {if (charCount[(int)word[i]] > 0) {charCount[(int)word[i]]--;} else if (wildcardCount > 0) {wildcardCount--;} else {return false;}}return true;
}int main() {int n;// 读取单词的数量printf("Enter number of words: ");scanf("%d", &n);char words[n][100];// 读取所有单词printf("Enter the words:\n");for (int i = 0; i < n; i++) {scanf("%s", words[i]);}// 读取可用字符的字符串char chars[100];printf("Enter available characters: ");scanf("%s", chars);// 输出掌握的单词个数int result = countMasteredWords(words, n, chars);printf("%d\n", result);return 0;
}

九、C++算法源码

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <cstring>using namespace std;int countMasteredWords(const vector<string>& words, const string& chars) {unordered_map<char, int> charCount;// 统计 chars 中每个字符的频率for (char ch : chars) {charCount[ch]++;}int masteredWordsCount = 0;// 验证每个单词是否可以由 chars 中的字符拼写出来for (const string& word : words) {unordered_map<char, int> tempCharCount = charCount;if (canSpell(word, tempCharCount)) {masteredWordsCount++;}}return masteredWordsCount;
}bool canSpell(const string& word, unordered_map<char, int>& charCount) {int wildcardCount = charCount['?'];for (char ch : word) {if (charCount[ch] > 0) {charCount[ch]--;} else if (wildcardCount > 0) {wildcardCount--;} else {return false;}}return true;
}int main() {int n;// 读取单词的数量cout << "Enter number of words: ";cin >> n;vector<string> words(n);// 读取所有单词cout << "Enter the words:" << endl;for (int i = 0; i < n; i++) {cin >> words[i];}// 读取可用字符的字符串string chars;cout << "Enter available characters: ";cin >> chars;// 输出掌握的单词个数int result = countMasteredWords(words, chars);cout << result << endl;return 0;
}