题目

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1：

  1. 输入：words = ["cat","bt","hat","tree"], chars = "atach"
  2. 输出：6
  3. 解释： 
  4. 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。


提示：

  1. 1 <= words.length <= 1000
  2. 1 <= words[i].length, chars.length <= 100
  3. 所有字符串中都仅包含小写英文字母

答案1

#
# @lc app=leetcode.cn id=1160 lang=python3
#
# [1160] 拼写单词
#

# @lc code=start
from typing import List


class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        ans = 0
        for word in words:
            for i in word:
                # word中某字符的数量 > chars中的对应字符的数量，条件不符合。
                if word.count(i) > chars.count(i):
                    break
            else:
                ans += len(word)  # 掌握的所有单词的 长度之和。
        print(ans)
        return ans


Solution().countCharacters(["cat", "bt", "hat", "tree"], "atach")
# @lc code=end

Note

word中某字符的数量 > chars中的对应字符的数量，条件不符合。
如果是 word 中出现的字符在 chars中没有则是 1 > 0

答案2

#
# @lc app=leetcode.cn id=1160 lang=python3
#
# [1160] 拼写单词
#

# @lc code=start
from typing import List

from collections import Counter


class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        chars_cnt = Counter(chars)
        ans = 0
        for word in words:
            # 转换哈希表
            word_cnt = Counter(word)
            for c in word_cnt:
                # 每一个字符的数量与 chars的哈希表中对应的字符数量 对比
                if chars_cnt[c] < word_cnt[c]:
                    break
            else:
                ans += len(word)
        print(ans)
        return ans


Solution().countCharacters(["cat", "bt", "hat", "tree"], "atach")
# @lc code=end

Note

哈希表记数

思路和算法
显然，对于一个单词 word，只要其中的每个字母的数量都不大于 chars 中对应的字母的数量，那么就可以用 chars 中的字母拼写出 word。所以我们只需要用一个哈希表存储 chars 中每个字母的数量，再用一个哈希表存储 word 中每个字母的数量，最后将这两个哈希表的键值对逐一进行比较即可。

from collections import Counter
colors = ['red', 'blue', 'red', 'green', 'blue', 'blue']
c = Counter(colors)
print (dict(c))


{'red': 2, 'blue': 3, 'green': 1}

python for 循环有一个大问题就是我们无法通过判断循环变量 i 来判断是否提前终止了，例如：

for i in range(10): 
    if i==9: 
        break

和

for i in range(10): 
    pass

最终变量 i 的值都会停在 9， 而不是第一个为 9， 第二个为 10. 需要额外引进一个 flag 变量来辅助判断。 例如：

flag = True
for i in range(10): 
    if i==9: 
        flag=False 
        break

然后判断 flag 是否为 False 来判断是否提前终止。
python 一定程度上为了弥补这一问题， 引入了 for .. else 结构。 这个 for … else… 中的 else 表示若循环有效结束，而不是提前终止，就执行 else 后面的语句，若提前终止，就不执行。这个 ‘else’ 和 if..else 中的else 语义不一样。或许用 then 更合适，但 python 之父不愿意再新定义一个关键字 then，就复用了这个 else
另外，这里 for 语句中的变量 i 非常特殊，例如下面的语句

for i in range(5): 
    i += 1 
    print(i) # 输出 [1,2,3,4,5]