难度:简单
给你一个由不同字符组成的字符串
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
只包含小写英文字母。
解题思路
看到题目的时候内心觉得soeay,遍历一下words里面的每个字符串的字符是否包含在allowed里面就行了。
代码
public int countConsistentStrings(String allowed, String[] words) {
//结果
int count = 0;
int index;
for (String s : words) {
for (index = 0; index < s.length(); index++) {
//判断一下是否在
if (!allowed.contains(s.charAt(index) + "")) {
break;
}
}
//如果循环没有被中断,那么index的值会等于字符串长度
if (index == s.length()) {
count++;
}
}
return count;
}
官方解题思路
由题意可知,字符串 allowed 和字符串数组 words 中的所有字符串都只包含小写字母,因此我们可以用一个 32 位整数来表示一个字符串出现的字母集合(二进制,每一位代表一个字母,低到高为a~z,多余的位不管)。如果一个字母出现了,那么将对应整数的位设为 1。使用 mask 表示字符串 allowed 出现的字母集合。依次遍历字符串数组 words,用mask1来表示每个字符串的包含的字母集合,如果每个字符串的mark1和mask的或运算等于mask,说明mark1的字符集被mask包含。
这样效率是我的代码的四倍,厉害哦~
代码
public int countConsistentStrings2(String allowed, String[] words) {
//先算出allowed的字符集,也就是第一位的1代表a,第二位的1代表b。。。
int mask = 0;
for (int i = 0; i < allowed.length(); i++) {
char c = allowed.charAt(i);
mask |= 1 << (c - 'a');
}
int res = 0;
for (String word : words) {
//算出每一个字符串的字符集
int mask1 = 0;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
mask1 |= 1 << (c - 'a');
}
//对比包含关系,注意这里括号不能省 |运算的优先级比较低
if ((mask1 | mask) == mask) {
res++;
}
}
return res;
}
网友评论