华为OD机试 - 掌握的单词个数 - 回溯（Java 2024 C卷 100分）

在这里插入图片描述

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

专栏导读

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

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有一个字符串数组 words 和一个字符串 chars。假如可以用 chars 中的字母拼写出 words 中的某个"单词"（字符串)，那么我们就认为你掌握了这个单词。

words 的字等仅由 a-z 英文小写宁母组成，例如“abc”。

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

注意: 每次拼写时，chars 中的每个字母和万能字符都只能使用一次。输出词汇表 words 中你掌握的所有单词的个数。没有掌握任何单词，则输出0。

二、输入描述

第一行: 输入数组 words 的个数，记作N。

第二行~第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??

2、输出

3、说明

可以掌握的单词 “cat”、“bt"和"hat”。

四、解题思路

遍历输入的 words 数组，对于每个单词，统计其每个字母的出现次数。
统计 chars 字符串中各字符的数量。
对于每个单词，检查其每个字母在 chars 中的数量是否足够，并且考虑万能字符"?"的情况。
如果单词中的每个字母在 chars 中都能够被拼写，则将该单词加入结果计数中。
返回最终的结果计数，即为掌握的单词个数。

五、Java算法源码

public class OdTest01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());

        String[] words = new String[n];
        for (int i = 0; i < n; i++) {
            words[i] = scanner.nextLine();
        }

        String chars = scanner.nextLine();

        System.out.println(getWordSum(words, n, chars));

        scanner.close();
    }

    public static int getWordSum(String[] words, int n, String chars) {
        int ret = 0;

        // 获取chars字符串中各字符的数量
        int[] arr = getCharSum(chars);

        for (int i = 0; i < n; i++) {
            int sum = 0;

            // 获取word字符串中各字符的数量
            int[] charSumArr = getCharSum(words[i]);

            for (int j = 0; j < 128; j++) {
                // word的字符超过chars的对应字符出现的数量
                sum += Math.max(charSumArr[j] - arr[j], 0);
            }

            if (sum <= arr['?']) {
                ret++;
            }
        }

        return ret;
    }

    /**
     * 获取word字符串中各字符的数量
     */
    public static int[] getCharSum(String str) {
        int[] arr = new int[128];

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            arr[c] += 1;
        }

        return arr;
    }
}