LeeCode刷題記錄4------拼寫(xiě)單詞(簡(jiǎn)單)

題目描述:

給你一份詞匯表(字符串?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ì)算。
在此題中:

  1. cLetter數(shù)組來(lái)存儲(chǔ)字母表中每個(gè)字母出現(xiàn)的次數(shù)。
  2. 對(duì)于每個(gè)單詞都創(chuàng)建一個(gè)wLetter數(shù)組來(lái)存儲(chǔ)該單詞所需的每個(gè)字母的個(gè)數(shù)。
  3. 比較cLetter數(shù)組和wLetter數(shù)組的對(duì)應(yīng)位置。
  4. 如果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;
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書(shū)系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容