Count the Number of Consistent Strings

Leetcode Problem:

• Count the Number of Consistent Strings

Summary

• Count the number of consistent strings in a given array of words, where a string is consistent if all characters appear in the allowed string.

Approach

• The solution uses a boolean array to track the presence of each character in the allowed string
• It then iterates over each word in the array, checking if each character in the word is present in the allowed string
• If a character is not present, the word is not consistent and is not counted.

Complexity

• O(n*m), where n is the length of the allowed string and m is the maximum length of a word in the array.

Explain

• The solution works by first initializing a boolean array `allow` of size 256, where each index corresponds to a lowercase English letter
• It then iterates over each character in the allowed string, setting the corresponding index in the `allow` array to `true`
• The solution then iterates over each word in the array, checking if each character in the word is present in the `allow` array
• If a character is not present, the word is not consistent and is not counted
• The number of consistent words is then returned.

Solution Code:

class Solution {
public:
    bool allow[256];
    int countConsistentStrings(string allowed, vector& words) {
        for(int i = 0 ; i < allowed.size(); i++){
            allow[allowed[i]] = true;
        }
        int ans = 0;
        for(int i = 0 ; i < words.size(); i++){
            bool success = true;
            for(int j = 0; j < words[i].size(); j++){
                if (!allow[words[i][j]]){
                    success = false;
                    break;
                }
            }
            if (success){
                ans++;
            }
        }
        return ans;
    }
};