1684. Count the Number of Consistent Strings - Explanation

1. Brute Force

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        res = 0

        for w in words:
            flag = 1
            for c in w:
                if c not in allowed:
                    flag = 0
                    break
            res += flag

        return res

Time & Space Complexity

Time complexity: $O(n * m * l)$
Space complexity: $O(1)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.

2. Hash Set

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        allowed = set(allowed)

        res = len(words)
        for w in words:
            for c in w:
                if c not in allowed:
                    res -= 1
                    break

        return res

Time & Space Complexity

Time complexity: $O(n * l + m)$
Space complexity: $O(m)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.

3. Boolean Array

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        allowedArr = [False] * 26
        for c in allowed:
            allowedArr[ord(c) - ord('a')] = True

        res = len(words)
        for w in words:
            for c in w:
                if not allowedArr[ord(c) - ord('a')]:
                    res -= 1
                    break

        return res

Time & Space Complexity

Time complexity: $O(n * l + m)$
Space complexity: $O(m)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.

4. Bitmask

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        bit_mask = 0
        for c in allowed:
            bit = 1 << (ord(c) - ord('a'))
            bit_mask = bit_mask | bit

        res = len(words)
        for w in words:
            for c in w:
                bit = 1 << (ord(c) - ord('a'))
                if bit & bit_mask == 0:
                    res -= 1
                    break

        return res

Time & Space Complexity

Time complexity: $O(n * l + m)$
Space complexity: $O(1)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.