所有子字符串中的元音
难度:
标签:
题目描述
代码结果
运行时间: 77 ms, 内存: 16.4 MB
/*
* Solution using Java Streams
*
* The approach is similar, but we use Java Streams to iterate over the characters.
* We filter out non-vowels, map the indices to the count of substrings they can form, and sum them.
*/
import java.util.stream.IntStream;
public class VowelSubstringCountStream {
public static long countVowels(String word) {
int n = word.length();
return IntStream.range(0, n)
.filter(i -> isVowel(word.charAt(i)))
.mapToLong(i -> (long) (i + 1) * (n - i))
.sum();
}
private static boolean isVowel(char c) {
return "aeiou".indexOf(c) >= 0;
}
public static void main(String[] args) {
System.out.println(countVowels("aba")); // Output: 6
System.out.println(countVowels("abc")); // Output: 3
System.out.println(countVowels("ltcd")); // Output: 0
System.out.println(countVowels("noosabasboosa")); // Output: 237
}
}
解释
方法:
此题解采用了一种高效的方法来计算字符串中所有子字符串的元音数。首先,将所有的元音字母存储在一个集合中,以便快速检查字符串中的每个字符是否为元音。遍历字符串中的每个字符,如果它是元音,就计算它在所有可能的子字符串中出现的次数。这可以通过计算它在左侧可能的起始位置数量(i+1)和右侧可能的结束位置数量(n-i)的乘积来得到。这样可以直接计算出每个元音字符对总元音数的贡献,而不需要生成所有子字符串。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在算法中选择使用集合来存储元音字母,而不是其他数据结构如列表或字典?
▷🦆
算法中提到的计算元音在所有子字符串中出现的次数的公式`(i + 1) * (n - i)`是如何得出的?能否详细解释这个计算过程?
▷🦆
在实现中使用了`enumerate`函数来遍历字符串,使用这种方式有什么特别的优势吗?
▷🦆
如果输入的字符串非常大,这种方法的性能表现如何?是否有可能优化内存使用?
▷