• 1684、统计一致字符串的数目(暴力+哈希)


    给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中,就称这个字符串是 一致字符串

    请你返回 words 数组中 一致字符串 的数目。

    示例 1:

    输入:allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
    输出:2
    解释:字符串 "aaab" 和 "baa" 都是一致字符串,因为它们只包含字符 'a' 和 'b' 。

    示例 2:

    输入:allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
    输出:7
    解释:所有字符串都是一致的。

    示例 3:

    输入:allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
    输出:4
    解释:字符串 "cc","acd","ac" 和 "d" 是一致字符串。

    解题思路:

     一、遍历

    通过判断words数组中每一行的字符串中的单个字符是否存在于allowed中,来判断该字符串是否为一致字符串;

    若字符存在于allowed中,则sum++,遍历完该字符串后sum的值应于当前字符串的大小相同,则表明该字符串为一致字符串,count++;

    最后返回count的值为words数组中一致字符串的数量。

    1. int countConsistentStrings(char * allowed, char ** words, int wordsSize){
    2. int count=0;
    3. for(int j=0;j
    4. {
    5. int sum=0;
    6. for(int i=0;i<strlen(allowed);i++)
    7. {
    8. for(int k=0;k<strlen(words[j]);k++)
    9. {
    10. if(words[j][k]==allowed[i])
    11. sum++;
    12. }
    13. }
    14. if(sum==strlen(words[j]))
    15. count++;
    16. }
    17. return count;
    18. }

    二、哈希算法 

    因为都是小写字母,所以可以用数组来代替哈希表

    将数组全部初始化为0;

    一次遍历 allowed ,将 allowed 出现的字符的位置在数组中标记为1;

    一次遍历words,统计当前字符串中的字符在数组中的位置为1的个数,与字符串大小进行比较,若相同则result++;

    最后返回result的值为words数组中一致字符串的数量。

    1. int countConsistentStrings (char * allowed, char ** words, int wordsSize)
    2. {
    3. int lib[26] = {0};
    4. for (int i = 0; allowed[i] != '\0'; ++i)
    5. {
    6. lib[allowed[i] - 'a'] = 1;
    7. }
    8. int result = 0;
    9. for (int i = 0; i < wordsSize; ++i)
    10. {
    11. int j = -1;
    12. int len = strlen(words[i]);
    13. while (++j < len && lib[words[i][j] - 'a'] == 1);
    14. result += j >= len;
    15. }
    16. return result;
    17. }
  • 相关阅读:
    LeetCode HOT 100 —— 75 .颜色分类
    新手程序员常见的编码错误
    Gitee的注册和代码提交
    Linux调试器-gdb使用
    transformers生成式对话机器人
    凌恩客户文章|宏基因组揭示大蒜素对抗生素抗性基因的影响
    MySQL优化01-索引
    关于亚马逊云科技云技能学习
    【Linux初阶】信号入门 | 信号基本概念+信号产生+核心转储
    CentOS安装NPM
  • 原文地址:https://blog.csdn.net/weixin_59179454/article/details/127756766