leetcode
leetcode 1801 ~ 1850
所有子字符串中的元音

所有子字符串中的元音

难度:

标签:

题目描述

代码结果

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

代码细节讲解

🦆
为什么在算法中选择使用集合来存储元音字母,而不是其他数据结构如列表或字典?
在算法中使用集合来存储元音字母主要是因为集合提供了更高效的查找性能。集合(在大多数现代编程语言中)通常是基于哈希表实现的,这使得平均情况下的查找时间复杂度为O(1)。相比之下,如果使用列表存储元音字母,每次查找字符是否为元音时都需要遍历整个列表,其时间复杂度为O(n),这在元音字母较多时会较慢。虽然使用字典也可以达到O(1)的查找性能,但相较于集合,字典会存储额外的键值对信息,对于只需要判断成员资格的场景而言,集合更加简洁高效。
🦆
算法中提到的计算元音在所有子字符串中出现的次数的公式`(i + 1) * (n - i)`是如何得出的?能否详细解释这个计算过程?
在给定的字符串中,每个字符都可以是多个子字符串的一部分。对于字符串中位置i的字符,它可以作为起始字符的子字符串的数量等于i+1(因为起始位置可以从0到i),它可以作为结束字符的子字符串的数量等于n-i(因为结束位置可以从i到n-1,共n-i个位置)。因此,位置i的字符在所有可能的子字符串中出现的次数就是它可以作为起始位置的子字符串数量乘以它可以作为结束位置的子字符串数量,即`(i + 1) * (n - i)`。这个公式有效地计算了一个字符在所有子字符串中的出现次数,而不需要实际生成这些子字符串,从而提高了算法的效率。
🦆
在实现中使用了`enumerate`函数来遍历字符串,使用这种方式有什么特别的优势吗?
使用`enumerate`函数遍历字符串可以同时获得每个字符及其在字符串中的索引。这比使用传统的循环计数器更为方便和直观,因为它避免了手动更新索引变量。在本算法中,需要知道每个字符的索引来计算它在子字符串中的出现次数,使用`enumerate`使得代码更简洁、易读,并减少了出错的可能性。
🦆
如果输入的字符串非常大,这种方法的性能表现如何?是否有可能优化内存使用?
如果输入的字符串非常大,这种算法的时间复杂度是O(n),其中n是字符串的长度,因为算法只需要遍历字符串一次。这是一个线性时间复杂度,对于大型输入来说已经是非常高效。在内存使用方面,算法主要消耗是存储元音集合和几个辅助变量,其空间复杂度为O(1),即常数级别。因此,从时间和空间效率来看,这种算法已经是相对优化的。然而,如果考虑到极端情况下的性能,可以考虑并行处理或使用更高效的硬件,但这已经是对算法外部环境的优化,而不是算法本身的改进。

相关问题