统计一致字符串的数目
难度:
标签:
题目描述
代码结果
运行时间: 44 ms, 内存: 18.2 MB
/*
* 思路:
* 1. 将allowed字符串转换为Set,用于快速查找字符。
* 2. 使用Java Stream对words数组进行处理。
* 3. 对每个单词,检查其每个字符是否都在allowedSet中。
* 4. 使用allMatch方法判断是否所有字符都满足条件,计数一致字符串。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;
public class ConsistentStringsStream {
public int countConsistentStrings(String allowed, String[] words) {
Set<Character> allowedSet = new HashSet<>();
for (char c : allowed.toCharArray()) {
allowedSet.add(c);
}
return (int) Stream.of(words)
.filter(word -> word.chars().allMatch(c -> allowedSet.contains((char)c)))
.count();
}
}
解释
方法:
首先,将字符串 `allowed` 中的所有字符存储到一个集合 `seen` 中,以便于快速检查一个字符是否属于 `allowed`。初始化答案 `ans` 为 `words` 数组的长度,即假设所有字符串初始时都是一致字符串。遍历 `words` 数组中的每个字符串,对于每个字符串,遍历其所有字符,检查是否每个字符都存在于 `seen` 集合中。如果发现有任何字符不在 `seen` 集合中,当前字符串不是一致字符串,将 `ans` 减一,并立即中断对当前字符串的检查(使用 `break`)。最后返回 `ans`。
时间复杂度:
O(n * m)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在确定一个字符串不是一致字符串后,可以立即中断对这个字符串的进一步检查?
▷🦆
题解中提到将allowed字符串中的字符存储在集合seen中,这种做法有什么优势?使用其他数据结构如列表或字典会如何影响性能?
▷🦆
如果allowed字符串或words数组为空,这个算法会有什么表现?题解中是否应该考虑这种边界情况?
▷🦆
题解中假设了所有字符串的初始状态是一致字符串,然后根据字符检查减少计数。是否有其他算法设计可以不需要预设初始计数,而是构建时计数增加?
▷