所有子字符串中的元音

难度: Medium

给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。

子字符串 是字符串中一个连续（非空）的字符序列。

注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。

示例 1：

输入：word = "aba"
输出：6
解释：
所有子字符串是："a"、"ab"、"aba"、"b"、"ba" 和 "a" 。
- "b" 中有 0 个元音
- "a"、"ab"、"ba" 和 "a" 每个都有 1 个元音
- "aba" 中有 2 个元音
因此，元音总数 = 0 + 1 + 1 + 1 + 1 + 2 = 6 。

示例 2：

输入：word = "abc"
输出：3
解释：
所有子字符串是："a"、"ab"、"abc"、"b"、"bc" 和 "c" 。
- "a"、"ab" 和 "abc" 每个都有 1 个元音
- "b"、"bc" 和 "c" 每个都有 0 个元音
因此，元音总数 = 1 + 1 + 1 + 0 + 0 + 0 = 3 。

示例 3：

输入：word = "ltcd"
输出：0
解释："ltcd" 的子字符串均不含元音。

示例 4：

输入：word = "noosabasboosa"
输出：237
解释：所有子字符串中共有 237 个元音。

提示：

1 <= word.length <= 10⁵
word 由小写英文字母组成

Submission

运行时间: 77 ms

内存: 16.4 MB

class Solution:
    def countVowels(self, word: str) -> int:
    
        vowels = set('aeiou')  # Define a set of vowels for quick lookup
        n = len(word)  # Length of the input string
        total_vowels = 0  # Initialize the count of vowels in all substrings

        # Iterate over each character in the word
        for i, char in enumerate(word):
            if char in vowels:
                # If the character is a vowel, calculate how many times it appears in all substrings
                total_vowels += (i + 1) * (n - i)

        return total_vowels

Explain

此题解采用了一种高效的方法来计算字符串中所有子字符串的元音数。首先，将所有的元音字母存储在一个集合中，以便快速检查字符串中的每个字符是否为元音。遍历字符串中的每个字符，如果它是元音，就计算它在所有可能的子字符串中出现的次数。这可以通过计算它在左侧可能的起始位置数量（i+1）和右侧可能的结束位置数量（n-i）的乘积来得到。这样可以直接计算出每个元音字符对总元音数的贡献，而不需要生成所有子字符串。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countVowels(self, word: str) -> int:
        vowels = set('aeiou')  # 定义一个包含所有元音的集合，以便快速查找
        n = len(word)  # 输入字符串的长度
        total_vowels = 0  # 初始化所有子字符串中元音的总数

        # 遍历字符串中的每个字符
        for i, char in enumerate(word):
            if char in vowels:  # 如果字符是元音
                # 计算该字符在所有子字符串中出现的次数
                total_vowels += (i + 1) * (n - i)

        return total_vowels  # 返回总元音数

Explore

在算法中使用集合来存储元音字母主要是因为集合提供了更高效的查找性能。集合（在大多数现代编程语言中）通常是基于哈希表实现的，这使得平均情况下的查找时间复杂度为O(1)。相比之下，如果使用列表存储元音字母，每次查找字符是否为元音时都需要遍历整个列表，其时间复杂度为O(n)，这在元音字母较多时会较慢。虽然使用字典也可以达到O(1)的查找性能，但相较于集合，字典会存储额外的键值对信息，对于只需要判断成员资格的场景而言，集合更加简洁高效。

在给定的字符串中，每个字符都可以是多个子字符串的一部分。对于字符串中位置i的字符，它可以作为起始字符的子字符串的数量等于i+1（因为起始位置可以从0到i），它可以作为结束字符的子字符串的数量等于n-i（因为结束位置可以从i到n-1，共n-i个位置）。因此，位置i的字符在所有可能的子字符串中出现的次数就是它可以作为起始位置的子字符串数量乘以它可以作为结束位置的子字符串数量，即`(i + 1) * (n - i)`。这个公式有效地计算了一个字符在所有子字符串中的出现次数，而不需要实际生成这些子字符串，从而提高了算法的效率。

使用`enumerate`函数遍历字符串可以同时获得每个字符及其在字符串中的索引。这比使用传统的循环计数器更为方便和直观，因为它避免了手动更新索引变量。在本算法中，需要知道每个字符的索引来计算它在子字符串中的出现次数，使用`enumerate`使得代码更简洁、易读，并减少了出错的可能性。

如果输入的字符串非常大，这种算法的时间复杂度是O(n)，其中n是字符串的长度，因为算法只需要遍历字符串一次。这是一个线性时间复杂度，对于大型输入来说已经是非常高效。在内存使用方面，算法主要消耗是存储元音集合和几个辅助变量，其空间复杂度为O(1)，即常数级别。因此，从时间和空间效率来看，这种算法已经是相对优化的。然而，如果考虑到极端情况下的性能，可以考虑并行处理或使用更高效的硬件，但这已经是对算法外部环境的优化，而不是算法本身的改进。