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

妖狐艹你老母 2024-05-11 09:27 84阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][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”。

### 四、解题思路 ###

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

### 五、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;
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

3  
hello  
world  
cloud  
welldonehohneyr

#### 2、输出 ####

#### 3、说明 ####

可以掌握的单词 “hello”、“world”。

![在这里插入图片描述][deee9d4b5b3d4c4abaa73c2c68bd2ae1.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

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

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/72de73a9c06d4251af35203c42453521.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[deee9d4b5b3d4c4abaa73c2c68bd2ae1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/caace4f78bb249319249e8cb074a9231.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/11/1917ee0521334be0a16ee08f82561c39.gif