Medium

题目描述

给定一个字符串 word，返回 word 中每个子串的元音字母（‘a’、’e’、‘i’、‘o’、‘u’）数量之和。

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

注意：由于约束条件较大，答案可能不适合有符号 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" 的任何子串中都没有元音。

约束条件：

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

解题思路

这题的关键思路是不要直接生成所有子串，而是计算每个元音字符在多少个子串中出现过。

数学分析方法： 对于位置 i 的元音字符，我们需要计算它会在多少个子串中出现：

  • 子串的左端点可以是 0 到 i，共 i + 1 种选择
  • 子串的右端点可以是 i 到 n - 1，共 n - i 种选择
  • 因此位置 i 的元音会在 (i + 1) * (n - i) 个子串中出现

动态规划方法： 定义 dp[i] 为以位置 i 结尾的所有子串的元音总数。转移方程为：

  • 如果 word[i] 是元音：dp[i] = dp[i-1] + i + 1
  • 如果 word[i] 不是元音：dp[i] = dp[i-1]

两种方法时间复杂度都是 O(n)，推荐使用数学方法，代码更简洁。

代码实现

class Solution {
public:
    long long countVowels(string word) {
        int n = word.length();
        long long result = 0;
        
        for (int i = 0; i < n; i++) {
            char c = word[i];
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                result += (long long)(i + 1) * (n - i);
            }
        }
        
        return result;
    }
};

class Solution:
    def countVowels(self, word: str) -> int:
        n = len(word)
        result = 0
        vowels = set('aeiou')
        
        for i, c in enumerate(word):
            if c in vowels:
                result += (i + 1) * (n - i)
        
        return result

public class Solution {
    public long CountVowels(string word) {
        int n = word.Length;
        long result = 0;
        var vowels = new HashSet<char> {'a', 'e', 'i', 'o', 'u'};
        
        for (int i = 0; i < n; i++) {
            if (vowels.Contains(word[i])) {
                result += (long)(i + 1) * (n - i);
            }
        }
        
        return result;
    }
}

var countVowels = function(word) {
    const n = word.length;
    let result = 0;
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    
    for (let i = 0; i < n; i++) {
        if (vowels.has(word[i])) {
            result += (i + 1) * (n - i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数学方法动态规划方法
时间复杂度O(n)O(n)
空间复杂度O(1)O(1)

其中 n 为字符串长度。两种方法时间复杂度相同，但数学方法空间复杂度更优，代码更简洁。

相关题目