华为OD机试 - 掌握单词个数（Java 2024 D卷 100分）

在这里插入图片描述

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

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷+A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天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个。

四、解题思路

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

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

五、Java算法源码

public class Test01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取单词的数量
        int n = Integer.parseInt(scanner.nextLine());
        String[] words = new String[n];

        // 读取所有单词
        for (int i = 0; i < n; i++) {
            words[i] = scanner.nextLine();
        }

        // 读取可用字符的字符串
        String chars = scanner.nextLine();
        scanner.close();

        // 输出掌握的单词个数
        System.out.println(countMasteredWords(words, chars));
    }

    public static int countMasteredWords(String[] words, String chars) {
        // 统计 chars 中每个字符的频率
        Map<Character, Integer> charCount = new HashMap<>();
        for (char ch : chars.toCharArray()) {
            charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);
        }

        int masteredWordsCount = 0;

        // 验证每个单词是否可以由 chars 中的字符拼写出来
        for (String word : words) {
            if (canSpell(word, new HashMap<>(charCount))) {
                masteredWordsCount++;
            }
        }

        return masteredWordsCount;
    }

    public static boolean canSpell(String word, Map<Character, Integer> charCount) {
        int wildcardCount = charCount.getOrDefault('?', 0);

        for (char ch : word.toCharArray()) {
            if (charCount.getOrDefault(ch, 0) > 0) {
                charCount.put(ch, charCount.get(ch) - 1);
            } else if (wildcardCount > 0) {
                wildcardCount--;
            } else {
                return false;
            }
        }

        return true;
    }
}