leetcode
leetcode 1501 ~ 1550
统计一致字符串的数目

统计一致字符串的数目

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么在确定一个字符串不是一致字符串后,可以立即中断对这个字符串的进一步检查?
在题解的算法中,字符串被定义为一致字符串当其所有字符都存在于集合 `seen` 中。一旦在字符串检查过程中发现有一个字符不在 `seen` 集合中,这个字符串就不满足一致字符串的条件。因此,没有必要继续检查该字符串的其他字符,因为已经确定这个字符串不能被计入一致字符串的总数。这种早停(early stopping)策略可以节省不必要的计算,提高算法效率。
🦆
题解中提到将allowed字符串中的字符存储在集合seen中,这种做法有什么优势?使用其他数据结构如列表或字典会如何影响性能?
将 `allowed` 字符串中的字符存储在集合 `seen` 中的主要优势在于集合提供了快速的成员检查操作,通常是O(1)时间复杂度。这是因为集合内部通常是基于哈希表实现的。相比之下,如果使用列表存储字符,成员检查操作的时间复杂度将为O(n),因为需要遍历整个列表来查找元素。使用字典存储字符虽然也能达到O(1)的检查性能,但相较于集合,字典会有额外的空间成本,因为它存储的是键值对而不仅仅是键。因此,使用集合是最优的选择,它提供了快速的查找速度并节省空间。
🦆
如果allowed字符串或words数组为空,这个算法会有什么表现?题解中是否应该考虑这种边界情况?
如果 `allowed` 字符串为空,则集合 `seen` 也将为空。这将导致 `words` 数组中的任何字符串都不会被认为是一致字符串,因为没有任何字符被允许。因此,算法将返回0。如果 `words` 数组为空,不论 `allowed` 如何,由于没有字符串需要检查,算法也将返回0。题解中已经隐式处理了这些情况,因为集合和循环逻辑自然会处理空集合和空数组的情况,无需额外代码。
🦆
题解中假设了所有字符串的初始状态是一致字符串,然后根据字符检查减少计数。是否有其他算法设计可以不需要预设初始计数,而是构建时计数增加?
可以设计一个算法,不预设初始计数,而是在检查过程中逐个增加计数。具体方法是初始化计数 `ans` 为0,遍历 `words` 数组中的每个字符串,对每个字符串进行检查,如果每个字符都在 `seen` 集合中,则将 `ans` 增加1。这种方法避免了初始假设所有字符串都是一致的,而是根据每个字符串的检查结果来动态增加计数,这在逻辑上可能更直观清晰,尤其是在处理大数据集时,可以避免在发现不一致字符串后对计数进行较多的减操作。

相关问题