arrays - 计算 C 中一致字符串的数量

Question

所以这是 leetcode 的一个问题，我遇到了一些问题。我已经看到解决这个问题的代码发布到 leetcode 的讨论部分，但我想知道是否有人可以帮助我解决它我已经编写了一些代码..这就是问题所在:

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'.

这是我到目前为止的代码:

注意:允许包含单个字符串

#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] 是否小于 strlen(允许)或反之亦然的问题..

我知道可能有更简单的方法来解决这个问题(正如我在 leetcode 的讨论部分看到的那样)，但我想知道是否有办法使用我已经完成的方法来解决它？

谢谢任何可以帮助我解决这个问题的人...我觉得我“几乎”遇到了这个问题，但我也已经被困在这个问题上很长一段时间了，所以我准备好接受任何解释我可以得到。

Answer 1

这是一个 O(N) 的解决方案。因此，您不必重新扫描每个字符的allowed，您只需使用查找表即可。很简单，因为字符通常是 8 位，并且 256 个真值/值的数组很容易。

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;
}