题目描述:
给你一份词汇表(字符串数组)words
和一张字母表(字符串)chars
。
假如你可以用 chars
中的字母(字符)拼写出 words 中的某个单词(字符串),那么我们就认为你掌握了这个单词。
注意:
每次拼写(指拼写词汇表中的一个单词)时,chars
中的每个字母都只能用一次。
返回词汇表 words
中你掌握的所有单词的 长度之和。
示例:
示例 1:
输入:words = ["cat","bt","hat","tree"], chars = "atach"
输出:6
解释:
可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。
示例 2:
输入:words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出:10
解释:
可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。
提示:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母
思路分析:
因为所有字符串仅包含小写的英文字母,那么我们就可以构建一个长度为26的字符数组,来分别表示每个字母的出现次数,以便进行对比和计算。
在此题中:
- 用
cLetter
数组来存储字母表中每个字母出现的次数。 - 对于每个单词都创建一个
wLetter
数组来存储该单词所需的每个字母的个数。 - 比较
cLetter
数组和wLetter
数组的对应位置。 - 如果
wLetter
数组中的数都不大于cLetter
数组中对应位置的数,那么说明改单词能够被拼写出来,则将该单词的长度计入返回结果中。
5.如果如果wLetter
数组中的数有一个大于了cLetter
数组中对应位置的数,则说明该单词不能被拼写出来,则无需进行其他字母的比较,直接跳转到下一个单词进行比较。
代码实现:
class Solution {
public int countCharacters(String[] words, String chars) {
int res = 0;
int[] cLetter = new int[26];
for (char c : chars.toCharArray()) {
cLetter[(int)(c - 'a')] += 1;
}
loop: for (int i = 0; i < words.length ; i++) {
int[] wLetter = new int[26];
for (char w : words[i].toCharArray()) {
wLetter[(int)(w - 'a')] += 1;
}
for (int j = 0; j < 26 ; j++) {
if (wLetter[j] > cLetter[j] ){
//只要判断出所需字母数大于已有字母数,结束当前的循环,跳转至下一个单词的对比判断
continue loop;
}
}
res = res + words[i].toCharArray().length;
}
return res;
}
}