拼写单词

难度: Easy

给你一份『词汇表』（字符串数组） 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
所有字符串中都仅包含小写英文字母

Submission

运行时间: 42 ms

内存: 16.3 MB

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        a=0
        for word in words:
            s=True
            for c in word:
                if word.count(c)>chars.count(c):
                    s=False
                    break
            if s:
                a=a+len(word)
        return a

Explain

此题解通过检查每个单词的每个字符是否可以由字符表`chars`中的字符组成来决定是否可以拼写该单词。对于每个单词，遍历其所有字符，使用字符串的`count`方法检查该字符在单词中出现的次数是否不超过该字符在字符表中的次数。如果所有字符都满足条件，则将该单词的长度累加到总长度中。

时间复杂度: O(L*(m+n))

空间复杂度: O(1)

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        a = 0  # 用于累加所有可以拼写的单词的长度
        for word in words:  # 遍历每个单词
            s = True  # 标志位，初始认为当前单词可以由chars拼写
            for c in word:  # 遍历单词中的每个字符
                if word.count(c) > chars.count(c):  # 如果单词中某字符c的数量超过chars中的数量
                    s = False  # 设置标志位为False
                    break  # 不再检查其他字符，直接结束当前单词的检查
            if s:  # 如果单词可以被拼写
                a += len(word)  # 将单词长度累加到a上
        return a  # 返回总长度

Explore

使用字符串的`count`方法是一种直观的方法来检查字符数量，尤其是在简单或较小的输入上效率尚可接受。然而，这种方法的时间复杂度较高，因为每次调用`count`都需要遍历整个字符串来统计字符。构建字符的哈希表（例如字典）可以显著优化查找和比较的效率，尤其是在处理大量数据或需要频繁查询的情况下。通过先统计每个字符的出现次数存入哈希表，之后的查找操作可以在常数时间内完成，从而减少整体的时间复杂度。

题解中提到的策略是有效的，因为一旦发现有一个字符不满足条件，整个单词就无法由`chars`拼写。这种提前终止检查的策略是优化性能的一种常见方式，可以避免对已确定无法拼写的单词进行更多无用的字符检查。然而，使用哈希表存储字符出现频率而非多次调用`count`方法也是减少不必要比较的一种方式，可以进一步提高效率。

如果`chars`为空，则无论`words`中的单词如何，都无法拼写任何单词，因为没有字符可用。如果`words`为空，则没有单词需要检查，因此返回的总长度应为0。处理这些边界情况是重要的，可以通过在函数开始添加简单的检查来实现。例如，如果`chars`为空或`words`为空，则直接返回0。这不仅可以避免不必要的计算，还可以防止潜在的运行时错误。