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.
1import java.util.Set;
2import java.util.HashSet;
3
4public class Main {
5 public int countConsistentStrings(String allowed, String[] words) {
6 Set<Character> allowedSet = new HashSet<>();
7 for (char c : allowed.toCharArray()) {
8 allowedSet.add(c);
9 }
10 int count = 0;
11 for (String word : words) {
12 boolean consistent = true;
13 for (char c : word.toCharArray()) {
14 if (!allowedSet.contains(c)) {
15 consistent = false;
16 break;
17 }
18 }
19 if (consistent) {
20 count++;
21 }
22 }
23 return count;
24 }
25}The Java solution uses a `HashSet` to manage the allowed characters. As we check each word, we ensure that every character exists in the set before incrementing the count of consistent strings.
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.