Leetcode 2020春招必刷61題-12

題目：拼寫單詞

給你一份『詞匯表』（字符串數組） 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
所有字符串中都僅包含小寫英文字母

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權，非商業(yè)轉載請注明出處。

思路：

起初看到這個題目，我的思路是利用一個for循環(huán)把詞匯表中每一個字符串的每一個字符與字母表的每一個字符單獨進行對比，如果相同則替換成空字符串，如果替換完成后詞匯表有空的字符串，我們則認為掌握了這個單詞，把這個單詞替換前的長度進行記錄，這個方法可能比較笨，但是我目前只想到這一種方法。說的可能比較繞，看一哈代碼就懂了。

代碼：

class Solution {
    public int countCharacters(String[] words, String chars) {
        int count = 0;
        for(String s : words){
            int length = s.length();
            for(int i=0; i<chars.length(); i++){
                String temp = String.valueOf(chars.charAt(i));
                s = s.replaceFirst(temp,"");
            }
            if(s.length() == 0) count += length;
        }
        return count;
    }
}

完事兒我又看了哈題解區(qū)大佬的思路，真的是被虐的體無完膚。在這里貼一下大佬的思路：
對于這道題，用數組c來保存字母表里每個字母出現的次數
如法炮制，再對詞匯表中的每個詞匯都做一數組w，比較數組w與數組c的對應位置
如果w中的都不大于c，就說明該詞可以被拼寫出，長度計入結果
如果w其中有一個超過了c，則說明不可以被拼寫，直接跳至下一個（這里用到了帶label的continue語法）

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] c = new int[26];
        for(char cc : chars.toCharArray()) {
            c[(int)(cc - 'a')] += 1;
        }
        int res = 0;
        a: for(String word : words) {
            int[] w = new int[26];
            for(char ww : word.toCharArray()) {
                w[(int)(ww - 'a')] += 1;
            }
            for(int i=0; i<26; i++) {
                if(w[i] > c[i]) {
                    continue a;
                }
            }
            res += word.length();
        }
        return res;
    }
}
作者：pendygg