Sponsored
Sponsored
We can leverage the power of sets to efficiently check if a word is consistent with the allowed characters. By converting the string `allowed` into a set, we can perform constant time look-up operations for each character in the words.
We will iterate through each word and check if every character of the word is present in the allowed set. If all characters are present, the word is consistent. Otherwise, it is not. We count the number of consistent words and return it.
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), as the space usage is dominated by the set of allowed characters, which is fixed at most 26.
1def countConsistentStrings(allowed, words):
2 allowed_set = set(allowed)
3 count = 0
4 for word in words:
5 if all(char in allowed_set for char in word):
6 count += 1
7 return countThis solution first converts the `allowed` string to a set so that we can efficiently check membership of each character. Then it iterates over each word and uses a generator expression to check if all characters in the word are in the `allowed_set`. If a word is consistent, it increments the count of consistent words.
An alternative approach to solve this problem is using bitmasking. We can represent the set of allowed characters as a bitmask, where each bit corresponds to a specific character ('a' could be the least significant bit and 'z' the most significant). This allows us to quickly check if a word is consistent by creating a bitmask of the word and verifying it against the allowed bitmask.
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), because we use a constant amount of extra space regardless of input size.
1def countConsistentStrings(allowed, words):
2In this Python implementation, we first create a bitmask for the allowed characters. Then, for each word, we convert it into a bitmask and check it against the allowed bitmask using bitwise operations. A word is consistent if its bitmask ANDed with the allowed mask produces the word mask itself.