统计一致字符串的数目

标签: 位运算 数组 哈希表 字符串

难度: Easy

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。

请你返回 words 数组中 一致字符串 的数目。

 

示例 1：

输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
输出：2
解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。

示例 2：

输入：allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
输出：7
解释：所有字符串都是一致的。

示例 3：

输入：allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
输出：4
解释：字符串 "cc"，"acd"，"ac" 和 "d" 是一致字符串。

 

提示：

  • 1 <= words.length <= 104
  • 1 <= allowed.length <= 26
  • 1 <= words[i].length <= 10
  • allowed 中的字符 互不相同 。
  • words[i] 和 allowed 只包含小写英文字母。

Submission

运行时间: 44 ms

内存: 18.2 MB

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        seen = set([ch for ch in allowed])
        ans = len(words)
        for w in words:
            for ch in w:
                if ch not in seen:
                    ans -= 1
                    break
        return ans

Explain

首先，将字符串 `allowed` 中的所有字符存储到一个集合 `seen` 中，以便于快速检查一个字符是否属于 `allowed`。初始化答案 `ans` 为 `words` 数组的长度，即假设所有字符串初始时都是一致字符串。遍历 `words` 数组中的每个字符串，对于每个字符串，遍历其所有字符，检查是否每个字符都存在于 `seen` 集合中。如果发现有任何字符不在 `seen` 集合中，当前字符串不是一致字符串，将 `ans` 减一，并立即中断对当前字符串的检查（使用 `break`）。最后返回 `ans`。

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

空间复杂度: O(1)

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        # 创建一个集合来快速检查字符是否被允许
        seen = set([ch for ch in allowed])
        # 初始化一致字符串的计数为所有单词的数量
        ans = len(words)
        # 遍历所有单词
        for w in words:
            # 检查单词中的每个字符
            for ch in w:
                # 如果字符不在允许的集合中，减少一致字符串的计数并停止检查这个单词
                if ch not in seen:
                    ans -= 1
                    break
        # 返回一致字符串的总数
        return ans

Explore

在题解的算法中，字符串被定义为一致字符串当其所有字符都存在于集合 `seen` 中。一旦在字符串检查过程中发现有一个字符不在 `seen` 集合中，这个字符串就不满足一致字符串的条件。因此，没有必要继续检查该字符串的其他字符，因为已经确定这个字符串不能被计入一致字符串的总数。这种早停（early stopping）策略可以节省不必要的计算，提高算法效率。

将 `allowed` 字符串中的字符存储在集合 `seen` 中的主要优势在于集合提供了快速的成员检查操作，通常是O(1)时间复杂度。这是因为集合内部通常是基于哈希表实现的。相比之下，如果使用列表存储字符，成员检查操作的时间复杂度将为O(n)，因为需要遍历整个列表来查找元素。使用字典存储字符虽然也能达到O(1)的检查性能，但相较于集合，字典会有额外的空间成本，因为它存储的是键值对而不仅仅是键。因此，使用集合是最优的选择，它提供了快速的查找速度并节省空间。

如果 `allowed` 字符串为空，则集合 `seen` 也将为空。这将导致 `words` 数组中的任何字符串都不会被认为是一致字符串，因为没有任何字符被允许。因此，算法将返回0。如果 `words` 数组为空，不论 `allowed` 如何，由于没有字符串需要检查，算法也将返回0。题解中已经隐式处理了这些情况，因为集合和循环逻辑自然会处理空集合和空数组的情况，无需额外代码。

可以设计一个算法，不预设初始计数，而是在检查过程中逐个增加计数。具体方法是初始化计数 `ans` 为0，遍历 `words` 数组中的每个字符串，对每个字符串进行检查，如果每个字符都在 `seen` 集合中，则将 `ans` 增加1。这种方法避免了初始假设所有字符串都是一致的，而是根据每个字符串的检查结果来动态增加计数，这在逻辑上可能更直观清晰，尤其是在处理大数据集时，可以避免在发现不一致字符串后对计数进行较多的减操作。