LC 1684. 统计一致字符串的数目

题目描述

这是 LeetCode 上的 1684. 统计一致字符串的数目 ，难度为 简单。

给你一个由不同字符组成的字符串 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 <= 10^4$
• $1 <= allowed.length <= 26$
• $1 <= words[i].length <= 10$
• allowed 中的字符 互不相同 。
• words[i] 和 allowed 只包含小写英文字母。

---

模拟

根据题意模拟即可：为了快速判断某个字符是否在 allowed 出现过，我们可以使用 Set 结构、定长数组或是一个 int 变量（搭配位运算）来对 allowed 中出现的字符进行转存。

随后遍历所有的 $words[i]$，统计符合要求的字符串个数。

Java 代码：

class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        boolean[] hash = new boolean[26];
        for (char c : allowed.toCharArray()) hash[c - 'a'] = true;
        int ans = 0;
        out:for (String s : words) {
            for (char c : s.toCharArray()) {
                if (!hash[c - 'a']) continue out;
            }
            ans++;
        }
        return ans;
    }
}

Java 代码：

class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        int hash = 0, ans = 0;
        for (char c : allowed.toCharArray()) hash |= (1 << (c - 'a'));
        out:for (String s : words) {
            for (char c : s.toCharArray()) {
                if (((hash >> (c - 'a')) & 1) == 0) continue out;
            }
            ans++;
        }
        return ans;
    }
}

TypeScript 代码：

function countConsistentStrings(allowed: string, words: string[]): number {
    const sset = new Set<string>()
    for (const c of allowed) sset.add(c)
    let ans = 0
    out:for (const s of words) {
        for (const c of s) {
            if (!sset.has(c)) continue out
        }
        ans++
    }
    return ans
}

TypeScript 代码：

function countConsistentStrings(allowed: string, words: string[]): number {
    let hash = 0, ans = 0
    for (const c of allowed) hash |= (1 << (c.charCodeAt(0) - 'a'.charCodeAt(0)))
    out:for (const s of words) {
        for (const c of s) {
            if (((hash >> (c.charCodeAt(0) - 'a'.charCodeAt(0))) & 1) == 0) continue out
        }
        ans++
    }
    return ans
}

Python3 代码：

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        sset = set([c for c in allowed])
        ans = 0
        for s in words:
            ok = True
            for c in s:
                if c not in sset:
                    ok = False
                    break
            ans += 1 if ok else 0
        return ans

Python3 代码：

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        num, ans = 0, 0
        for c in allowed:
            num |= (1 << (ord(c) - ord('a')))
        for s in words:
            ok = True
            for c in s:
                if not (num >> (ord(c) - ord('a')) & 1):
                    ok = False
                    break
            ans += 1 if ok else 0
        return ans

• 时间复杂度：$O(m + \sum_{i = 0}^{n - 1}words[i].length)$，其中 $m$ 为 allowed 长度，$n$ 为 words 长度
• 空间复杂度：$O(m)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1684 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。