1684. 统计一致字符串的数目【leetcode每日一题】

字符串的数目【leetcode每日一题】"/>

1684. 统计一致字符串的数目【leetcode每日一题】

给你一个由不同字符组成的字符串 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" 是一致字符串。

提示：

• 1 <= words.length <= 104
• 1 <= allowed.length <= 26
• 1 <= words[i].length <= 10
• allowed 中的字符 互不相同 。
• words[i] 和 allowed 只包含小写英文字母。

以上是题目的描述。

看到这个题呢，我的第一想法是直接暴力，就是对words字符串数组里的每个字符都和allowed里的字符遍历比较，但是时间复杂度会蛮大的。如果不考虑限制，n个字符比较的话可能会导致的时间复杂度。

如果把这个问题看作一个集合之间是否包含的问题，就不用考虑在words数组中重复字符的问题。把allowed字符串看作一个集合，把words数组中的每一个字符串看作一个集合。同时用构造hash数组的方法把allowed字符串中的每个字符映射到hash数组中，就方便words中的字符进行查找比较。

构造hash数组的方法：

int hash[26]={0};//因为题目说明allowed不超过26，且不能重复
char *p=allowed;
while(*p !='\0')
{hash[(int)(*p-'a')]++;p++;
}

这段代码的解释：

(*p-'a')字符对应的ASCII码进行运算，运算结果是ASCII码所对应的那个字符。在前面加上（int）表示强制转换类型。hash[(int)(*p-'a')]++作用是将(int)(*p-'a')结果映射到hash数组里，并且使对应数组中的元素自增1，就将当前字符映射到了这个数组的元素当中。以该元素的值为1，表示映射存在，通过p++进行字符串中字符的下一个滚动，这样通过有限次循环就能将allowed数组中的的每一个字符映射到hash数组中。

之后就开始将words数组中的字符串进行同样的方法进行映射查找，同时通过count和flag两个变量完成计数和做记号。代码如下：

int count=0;
int flag=0;
for(int i=0;i<wordsSize;i++)
{p=words[i];while(*p !='\0'){if(hash[(int)(*p-'a')]>0)//将words数组中字符串的每一个字符用同样的方法进行映射，写成表达式进行查找。{flag=1;p++;}else{flag=0;//但凡有一个字符不在hash数组之中，就将记号赋0，同时break推出当前while循环break;}}if(flag==1){count++;flag=0;//因为记号一直在使用，所以进入下一个for循环时，要将记号初始化赋0}
}

这个思想的两大工作就已经通过上面代码实现了，就是将allowed字符串的每一个字符映射到hash数组中，之后再对words数组中的字符通过同样的映射，再进行查找。时间复杂度为。

完整代码如下：

int countConsistentStrings(char * allowed, char ** words, int wordsSize){int hash[26]={0};int count=0;int flag=0;char *p=allowed;//构建allowed字符串哈希表while(*p !='\0'){hash[(int)(*p-'a')]++;p++;}/*(*p-'a')字符对应的ASCII码进行运算，运算结果是ASCII码所对应的那个字符在前面加上（int）表示强制转换类型hash[(int)(*p-'a')]++作用是将(int)(*p-'a')结果映射到hash数组里，并且使那个元素自增1*/for(int i=0;i<wordsSize;i++){p=words[i];while(*p !='\0'){if(hash[(int)(*p-'a')]>0){flag=1;p++;}else{flag=0;break;}}if(flag==1){count++;flag=0;}}return count;
}