题目描述
给你一份字符串数组 words
和一个字符串 chars
。
假如你可以用 chars
中的字符拼写出 words
中的某个字符串,那么我们就认为这个字符串是好的。每次拼写时,chars 中的每个字母都只能用一次。
返回词汇表 words
中好单词的长度之和。
样例
输入:words = ["cat","bt","hat","tree"], chars = "atach"
输出:6
解释:
可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。
输入:words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出:10
解释:
可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。
提示
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
- 所有字符串中都仅包含小写英文字母。
算法
(暴力枚举) $O(nL + m)$
- 统计出
chars
每种字母的出现次数。 - 枚举字符串数组
words
中的word
,对于每个word
,我们求出它每种字母的出现次数。如果每种字母的出现次数都小于等于chars
中对应字母的出现次数,则答案累计上该word
的长度。
时间复杂度
- 假设
chars
的长度为 $m$,字符串数组一共有 $n$ 个单词,每个单词平均长度为 $L$。 - 步骤 1 的时间复杂度为 $O(m)$,步骤 2 的时间复杂度为 $O(nL)$,故总时间复杂度为 $O(nL + m)$。
空间复杂度
- 仅需要常数个长度为 26 的数组,记录每种字母的出现次数,故空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
int countCharacters(vector<string>& words, string chars) {
int ans = 0;
vector<int> seen(26, 0);
for (char &c : chars)
seen[c - 'a']++;
for (auto &word : words) {
vector<int> cur(26, 0);
for (char &c : word)
cur[c - 'a']++;
bool flag = true;
for (int i = 0; i < 26; i++)
if (cur[i] > seen[i])
flag = false;
if (flag)
ans += word.length();
}
return ans;
}
};