# 1160. Find Words That Can Be Formed by Characters 拼写单词

@TOC

## # 题目描述

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.

## # 解题方法

### # 字典统计

1. 使用字典统计给出的字母表中每个字符出现的次数；
2. 使用字典统计词汇表中每个单词中的每个字符出现的次数；
3. 如果该单词中的每个字符出现的次数都小于字母表中对应字符出现的次数，那么说明可以使用字母表构成该单词。

C++代码如下：

``````class Solution {
public:
int countCharacters(vector<string>& words, string chars) {
unordered_map<char, int> chars_count;
for (char c : chars) {
chars_count[c] ++;
}
int res = 0;
for (string& word : words) {
unordered_map<char, int> word_count;
for (char c: word) {
word_count[c] ++;
}
bool can_form = true;
for (auto& wc_iter : word_count) {
if (chars_count[wc_iter.first] < wc_iter.second) {
can_form = false;
break;
}
}
if (can_form) {
res += word.size();
}
}
return res;
}
};
``````

## # 日期

2020 年 3 月 17 日 —— 很久没有做新题了