统计字符串中的元音子字符串
难度:
标签:
题目描述
代码结果
运行时间: 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 时,为什么选择这种方式而不是直接从头开始检查每个子字符串?
▷🦆
在处理非元音字符时,`self.clear(counter)` 方法立即清空计数器并重置 start 的位置,这样的处理是否会导致漏掉某些潜在的有效子字符串?
▷🦆
在缩小窗口的过程中,为何 `left` 指针在不满足所有元音都至少出现一次后,还要回退一步并调整计数器?
▷🦆
算法中如何保证不会重复计算相同的元音子字符串?
▷