leetcode
leetcode 1801 ~ 1850
统计字符串中的元音子字符串

统计字符串中的元音子字符串

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 0.0 MB


/*
 * 思路:
 * 使用Java Stream API来处理字符串。通过生成所有可能的子串,然后过滤包含所有五个元音的子串。
 */
import java.util.stream.IntStream;

public class VowelSubstringStream {
    public long countVowelSubstrings(String word) {
        int n = word.length();
        return IntStream.range(0, n)
                .boxed()
                .flatMap(i -> IntStream.range(i + 5, n + 1)
                        .mapToObj(j -> word.substring(i, j)))
                .filter(this::containsAllVowels)
                .count();
    }

    private boolean containsAllVowels(String s) {
        return s.contains("a") && s.contains("e") && s.contains("i") && s.contains("o") && s.contains("u");
    }

    public static void main(String[] args) {
        VowelSubstringStream solution = new VowelSubstringStream();
        System.out.println(solution.countVowelSubstrings("aeiouu")); // 输出: 2
        System.out.println(solution.countVowelSubstrings("unicornarihan")); // 输出: 0
        System.out.println(solution.countVowelSubstrings("cuaieuouac")); // 输出: 7
        System.out.println(solution.countVowelSubstrings("bbaeixoubb")); // 输出: 0
    }
}

解释

方法:

此题解采用了滑动窗口的策略来寻找包含所有五个元音至少各一次的最长子字符串。首先,我们使用三个指针 start, left 和 right 来定义当前探索的子字符串。我们从左到右遍历字符串,使用一个计数器来统计各个元音字母的出现次数。当我们遇到一个非元音字符时,我们将清空计数器并将 start 移动到 right 的位置。如果在 right 指针的位置我们发现所有五个元音都至少出现一次,我们就尝试从 left 开始减少窗口的大小直到不满足条件为止。这个过程中,我们计算从 start 到 left-1 所有可能的元音子字符串的数量并累加到结果中。每找到一个有效的子字符串后,我们调整 left 指针并尝试寻找新的子字符串。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在初始化三个指针 start, left, right 时,为什么选择这种方式而不是直接从头开始检查每个子字符串?
使用 start, left, 和 right 三个指针作为滑动窗口的策略可以有效减少不必要的计算。这种方法允许我们动态地调整窗口的大小来寻找包含所有五个元音至少一次的子字符串。如果从头开始检查每个子字符串,则每次都需要重新计算元音的出现次数,这会导致大量重复的计算,尤其是在字符串较长时。滑动窗口策略可以在扩展和缩小窗口时,通过简单的计数器调整来更新元音的计数,大大提高了效率。
🦆
在处理非元音字符时,`self.clear(counter)` 方法立即清空计数器并重置 start 的位置,这样的处理是否会导致漏掉某些潜在的有效子字符串?
处理非元音字符时,清空计数器并重置 start 的位置是必要的,因为题目要求的是找到仅包含元音字母的子字符串。遇到非元音字符意味着当前子字符串不再满足条件,因此必须重新开始搜索新的潜在子字符串。这种处理方式不会漏掉有效子字符串,因为一旦包含非元音字符,子字符串就不再符合题目要求。
🦆
在缩小窗口的过程中,为何 `left` 指针在不满足所有元音都至少出现一次后,还要回退一步并调整计数器?
在缩小窗口的过程中,当 `left` 指针移动导致某个元音的数量减少到零,即不满足所有元音至少出现一次的条件时,我们需要回退 `left` 指针一步并调整计数器,是为了保证在下一次循环中,窗口仍然是有效的起始点。这样,我们可以继续从这个点开始尝试寻找新的有效子字符串。这一步骤是确保算法正确性的关键,它使得每个可能的起始点都能被正确计算。
🦆
算法中如何保证不会重复计算相同的元音子字符串?
算法通过动态地调整 `start` 和 `left` 指针来确保每个元音子字符串只被计算一次。在找到一个包含所有元音至少一次的子字符串后,我们通过逐步移动 `left` 指针并减少窗口大小直到不再满足条件,这一过程中计算的是从 `start` 到 `left-1` 的所有可能子字符串数量。随后,通过适当调整 `start` 和 `left` 指针来开始新的搜索,避免了重复计算。

相关问题