Count the Number of Consistent Strings in C

user_5844430 0
Viewed 622

So this is a problem off leetcode and I'm having some issues with it.. I've seen code that solves this problem posted to the discussion's portion of leetcode, but I was wondering if anyone could help me solve it with some of the code I've already written.. Here's what the problem is asking:

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed. Return the number of consistent strings in the array words.

Example:
Input: allowed = "ab", words => ["ad","bd","aaab","baa","badab"]

Output: 2

Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Here's my code so far:

Note: allowed contains a single string

#include <string.h>

int countConsistentStrings(char * allowed, char ** words, int wordsSize){
    
    int real_count = 0;
    for(int i = 0; i < wordsSize; i++)
    {
        for(int j = 0; j < strlen(allowed); j++)
        {
            for(int k = 0; k < strlen(words[i]); k++)
            {
                if(words[i][k] != allowed[j])
                {
                    // stuff goes here?
                }
            }

        }
    }


    return real_count;
}

I'm able to iterate through the strings in the array char by char and compare them to allowed's chars... But I really don't know where to go from there. I've tried keeping tallies of stuff and using comparisons but then I run into issues of whether words[i] is less than strlen(allowed) or vice-versa..

I know there's probably easier ways to do this problem (as I've seen posted on the discussion portion of leetcode) but I'm wondering if there's anyway to solve it using what I've already done?

Thank you anyone who can help me out with this... I feel like I'm "almost" there with this problem, but I've also been stuck on it quite a while so I'm ready for any explanations I can get.

c arrays string
3 Answers

Here's an O(N) solution. So you don't have to rescan allowed for each character, you can just use a lookup table. Easy since chars are typically 8-bit and an array of 256 true/value values is easy.

int countConsistentStrings(char * allowed, char ** words, int wordsSize) {

    // put all the allowed chars into a table of booleans

    unsigned int table[256] = {0}; // 256 assumes 8-bit char
    int real_count = 0;
    const char* ptr = allowed;

    while (*ptr)
    {
        char c = *ptr;
        table[(unsigned char)c)] = 1;   // table[c] = 1 to indicate "is allowed"
        ptr++;
    }

    // evaluate each word and see if each char in word
    // is in the allowed list of chars
    
    for(int i = 0; i < wordsSize; i++)
    {
        char* word = words[i];
        int consistent = 1;
        while (*word && consistent)
        {
            char c = *word;
            consistent = table[(unsigned char)c]; // lookup to see if this char is allowed
            word++;
        }
        real_count += consistent;
    }

    return real_count;
}
user_1044580

You can use strchr function to help detect if a character exists in allowed. The function works like this:

   char *strchr(const char *s, int c);
   The strchr() function returns a pointer to the first occurrence
   of the character c in the string s.
   The strchr() and strrchr() functions return a pointer to the
   matched character or NULL if the character is not found.

So testing for NULL allows you to check if the character in question is found in allowed. With this function, you can remove one of your loops and just iterate through each character in a given word looking for matches. With this in mind, I think it's easier to assume all words do match then subtract out the ones that don't match.

Here is some code that illustrates what I mean. I created a main function that calls countConsistentStrings with some test data I used to verify the behavior.

#include <stdio.h>
#include <string.h>

int countConsistentStrings(char *allowed, char **words, int wordsSize)
{
    int real_count = wordsSize;
    for(int i = 0; i < wordsSize; i++)
    {
        for(int k = 0; k < strlen(words[i]); k++)
        {
            // if character is not found, then it's not a consistent string
            // so we can just lower the count and exit the loop right now
            if(strchr(allowed, words[i][k]) == NULL)
            {
                real_count--;
                break;
            }
        }
    }

    return real_count;
}

int main()
{
    char *allowed = "abcde";
    char *words[] =
    {
       "abcde",
       "fghji",
       "d",
       "l",
       "abcdef"
    };
    int wordcount = sizeof(words)/sizeof(words[0]);
    int count;

    printf("Finding consistent strings among %d words\n", wordcount);
    
    count = countConsistentStrings(allowed, words, wordcount);
    
    printf("Consistent string count: %d\n", count);

    return 0;
}
user_139242690

Assuming standard C library functions are allowed, the following uses size_t strspn(const char *dest, const char *src), which "returns the length of the maximum initial segment (span) of the null-terminated byte string pointed to by dest, that consists of only the characters found in the null-terminated byte string pointed to by src.".

#include <string.h>

int countConsistentStrings(char *allowed, char **words, int wordsSize)
{
    int count = 0;
    for(int i = 0; i < wordsSize; i++)
    {
        char *word = words[i];
        if(word[strspn(word, allowed)] == '\0')
            count++;
    }
    return count;
}
user_55384200
Related