[LeetCode] 1160、拼写单词_请你一“单词表”(字符串数组)

题目描述

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。返回词汇表 words 中你掌握的所有单词的 长度之和。

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释：可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
1
2
3

解题思路

做算法题要有举一反三的能力，学会总结，比如这个题就可以转换成一个字符出现次数的计数题。简单题，直接统计字母表 chars 中每个字母出现的次数，然后检查词汇表 words 中的每个单词，如果该单词中每个字母出现的次数都小于等于词汇表中对应字母出现的次数，就将该单词长度加入答案中。

参考代码

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> chars_map;
        for(auto c: chars)
            chars_map[c]++;

        int res = 0;
        for(auto word: words){
            bool invalid = false;  // 这里debug了好久，之前没有及时更新invalid的状态
            unordered_map<char, int> word_map;
        
            for(auto c: word)
                word_map[c]++;
            
            for(auto c: word){
                if(word_map[c] > chars_map[c]){
                    invalid = true;
                    break;
                }
            }
            
            if(!invalid)
                res += word.size();
        }
        
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29