[LeetCode] 1160. Find Words That Can Be Formed by Characters

[grandyang]

You are given an array of strings words and a string chars.

A string is  good  if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation:
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation:
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

1. 1 <= words.length <= 1000
2. 1 <= words[i].length, chars.length <= 100
3. All strings contain lowercase English letters only.

这道题给了一个单词数组 words，还有一个字符串 chars，定义了一种好字符串，说是能由 chars 中的字母组成的单词，限定每个字母只能使用一次，不必都使用，求所有好字符串的长度之和。既然是 Easy 的身价，自然不会用到太 fancy 的解法，就是一个单纯的字母统计问题，建立 chars 字符串中每个字母和其出现次数之间的映射，然后遍历每个单词，拷贝一个 chars 字符串的 HashMap，然后遍历当前单词的每个字母，对应字母的映射值减1，若为负数了，表示 chars 中缺少必要的单词，标记为 false。若最终为 true，则将当前单词的长度加入结果 res 中即可，参见代码如下：

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int res = 0;
        unordered_map<char, int> charCnt;
        for (char c : chars) ++charCnt[c];
        for (string word : words) {
            unordered_map<char, int> m = charCnt;
            bool succeed = true;
            for (char c : word) {
                if (--m[c] < 0) {
                    succeed = false;
                    break;
                }
            }
            if (succeed) res += word.size();
        }
        return res;
    }
};

Github 同步地址:

#1160

参考资料：

https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/

https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/discuss/360978/C%2B%2B-Track-Count

LeetCode All in One 题目讲解汇总(持续更新中...)