1160. Find Words That Can Be Formed by Characters - chasel2361/leetcode GitHub Wiki

You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.

Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation:
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation:
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

這個題目要求檢查給定 words 中的 string 是否可由給定的 char 組成

一開始沒有看得很懂，以為只要 string 中的字母有在 char 裡面就可以，所以寫成下面這樣

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        n = 0
        for word in words:
            good = True
            for char in word:
                if char not in chars:
                    good = False
                    break
        
            if good == True:
                n += len(word)
        return n

這個寫法沒有考慮到字母的個數，所以不是正確解，應該要利用 string.count(char) 來計算字母出現 word 中出現的個數是否小於 char 中。

不過如果遇到很長的字串這樣的效率會變低，所以使用 Counter 來減輕負擔，這個物件會將輸入的字串分割成 dict ，字母做為 key、個數作為 value。如此便將空間節省至最多 26 個字母及其出現次數，寫為程式碼如下。

from collections import Counter
class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        dic = Counter(chars)
        n = 0
        for word in words:
            good = True
            dic_c = Counter(word)
            for key, value  in dic_c.items():
                if key not in dic.keys() or value > dic[key]:
                    good = False
                    break
            if good == True:
                n += len(word)
        return n

後來想了想，覺得要一直利用 good 來做判斷有點麻煩，所以多加了一個函式讓程式碼精簡一點

from collections import Counter
class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        def check(word):
            dic_check = Counter(word)
            for key, value in dic_check.items():
                if key not in dic.keys() or value > dic[key]:
                    return 0
            return len(word)
        
        dic = Counter(chars)
        n = 0
        for word in words:
            n += check(word)
        return n

這樣寫的時間複雜度是 O(N)，空間複雜度是O(1)