LeetCode學習筆記——單詞拼寫

個人部落格：The Blog Of WaiterXiaoYY 歡迎來互相交流學習。

1160. 拼寫單詞

給你一份『詞彙表』（字元串數組） 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.利用長度為26的數組，例如int []chars = new int[26]

2.記錄單詞表中每個word中各自字元出現的數量，同時也記錄chars中字元的數量

3.對單詞表words中的每個word進行周遊，當chars中的某字元數量小于word的字元數量時，則說明該單詞不能被掌握，标記後跳過這個單詞，周遊下一個。

需要注意的是，在進行統計一個字元串中每個字元的數量的時候，要将字元串轉為數組的形式，

即String.toCharArray()，此時才可以對其進行挨個周遊。

代碼

public int countCharacters(String[] words, String chars) {
    if(chars == null || words == null)
        return 0;
    int []cnt_chars = new int[26];   //用于統計chars中字元的數量
    int count = 0;  //單詞長度計數
    int flag = 1;   //标記，用于判斷該單詞是否能被掌握
    //對chars進行周遊統計
    for(char c : chars.toCharArray())
        cnt_chars[c - 'a']++;
    //對單詞表中每個word進行單獨操作
    for(String word : words) {
        int []cnt_word = new int[26];   
        //統計每個單詞字元的數量
        for(char c : word.toCharArray())
            cnt_word[c - 'a']++;
        //再次對該單詞進行周遊，判斷是否能被掌握
        for(char c : word.toCharArray()) {
            //如果chars中的字元數量小于word中，則标記不能被掌握，跳過這個單詞
            if(cnt_chars[c - 'a'] < cnt_word[c - 'a']) {
                flag = 0;
                break;
            }
            flag = 1;  //需将标記更新
        }
        if(flag == 1)
            count += word.length();  //将單詞長度加起來
    }
    return count;
}