2024年华为OD机试真题-万能字符单词拼写

华为OD机试真题-万能字符单词拼写-2024年OD统一考试（D卷）

题目描述：

有一个字符串数组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 <= words.length <= 100

1 <= words[i].length, chars.length <= 100

所有字符串中都仅包含小写英文字母、英文问号

示例1

输入：

4

cat

bt

hat

tree

atach??

输出：

3

说明：

可以拼写字符串"cat"、"bt"和"hat"

示例2

输入：

3

hello

world

cloud

welldonehoneyr

输出：

2

说明：

可以拼写字符串"hello"和"world"

示例3

输入：

3

apple

car

window

welldoneapplec?

输出：

2

说明：

可以拼写字符串"apple"和"car"

解题思路：

考察数组，可以使用哈希表和字符串处理。

c++解法：

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int getResult(vector<string> words, int n, string chars) {
    int ans = 0;
 
    vector<int> cnt_chars(128, 0);
    for (char c : chars) {
        cnt_chars[c]++;
    }
 
    for (int i = 0; i < n; i++) {
        int diff = 0;
 
        vector<int> cnt_word(128, 0);
        for (char c : words[i]) {
            cnt_word[c]++;
        }
 
        for (int j = 0; j < 128; j++) {
 
            diff += max(cnt_word[j] - cnt_chars[j], 0);
        }
 
        if (diff <= cnt_chars['?']) {
            ans++;
 
        }
    }
 
    return ans;
}
 
int main() {
    int n;
    cin >> n;
 
    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }
 
    string chars;
    cin >> chars;
 
    cout << getResult(words, n, chars) << endl;
 
    return 0;
}

Java解法