題目描述:
給你一份詞匯表(字符串?dāng)?shù)組)words 和一張字母表(字符串)chars。
假如你可以用 chars中的字母(字符)拼寫(xiě)出 words 中的某個(gè)單詞(字符串),那么我們就認(rèn)為你掌握了這個(gè)單詞。
注意:
每次拼寫(xiě)(指拼寫(xiě)詞匯表中的一個(gè)單詞)時(shí),chars 中的每個(gè)字母都只能用一次。
返回詞匯表 words 中你掌握的所有單詞的 長(zhǎng)度之和。
示例:
示例 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
所有字符串中都僅包含小寫(xiě)英文字母
思路分析:
因?yàn)樗凶址畠H包含小寫(xiě)的英文字母,那么我們就可以構(gòu)建一個(gè)長(zhǎng)度為26的字符數(shù)組,來(lái)分別表示每個(gè)字母的出現(xiàn)次數(shù),以便進(jìn)行對(duì)比和計(jì)算。
在此題中:
- 用
cLetter數(shù)組來(lái)存儲(chǔ)字母表中每個(gè)字母出現(xiàn)的次數(shù)。 - 對(duì)于每個(gè)單詞都創(chuàng)建一個(gè)
wLetter數(shù)組來(lái)存儲(chǔ)該單詞所需的每個(gè)字母的個(gè)數(shù)。 - 比較
cLetter數(shù)組和wLetter數(shù)組的對(duì)應(yīng)位置。 - 如果
wLetter數(shù)組中的數(shù)都不大于cLetter數(shù)組中對(duì)應(yīng)位置的數(shù),那么說(shuō)明改單詞能夠被拼寫(xiě)出來(lái),則將該單詞的長(zhǎng)度計(jì)入返回結(jié)果中。
5.如果如果wLetter數(shù)組中的數(shù)有一個(gè)大于了cLetter數(shù)組中對(duì)應(yīng)位置的數(shù),則說(shuō)明該單詞不能被拼寫(xiě)出來(lái),則無(wú)需進(jìn)行其他字母的比較,直接跳轉(zhuǎn)到下一個(gè)單詞進(jìn)行比較。
代碼實(shí)現(xiàn):
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] ){
//只要判斷出所需字母數(shù)大于已有字母數(shù),結(jié)束當(dāng)前的循環(huán),跳轉(zhuǎn)至下一個(gè)單詞的對(duì)比判斷
continue loop;
}
}
res = res + words[i].toCharArray().length;
}
return res;
}
}