2063. 所有子字符串中的元音

题目描述

给你一个字符串 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 由小写英文字母组成

解法

方法一：枚举贡献

我们可以枚举字符串的每个字符 \(\textit{word}[i]\)，如果 \(\textit{word}[i]\) 是元音字母，那么 \(\textit{word}[i]\) 一共在 \((i + 1) \times (n - i)\) 个子字符串中出现，将这些子字符串的个数累加即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(\textit{word}\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRustJavaScript

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

class Solution {
    public long countVowels(String word) {
        long ans = 0;
        for (int i = 0, n = word.length(); i < n; ++i) {
            char c = word.charAt(i);
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                ans += (i + 1L) * (n - i);
            }
        }
        return ans;
    }
}

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

func countVowels(word string) (ans int64) {
    for i, c := range word {
        if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
            ans += int64((i + 1) * (len(word) - i))
        }
    }
    return
}

function countVowels(word: string): number {
    const n = word.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (['a', 'e', 'i', 'o', 'u'].includes(word[i])) {
            ans += (i + 1) * (n - i);
        }
    }
    return ans;
}

impl Solution {
    pub fn count_vowels(word: String) -> i64 {
        let n = word.len() as i64;
        word.chars()
            .enumerate()
            .filter(|(_, c)| "aeiou".contains(*c))
            .map(|(i, _)| (i as i64 + 1) * (n - i as i64))
            .sum()
    }
}

/**
 * @param {string} word
 * @return {number}
 */
var countVowels = function (word) {
    const n = word.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (['a', 'e', 'i', 'o', 'u'].includes(word[i])) {
            ans += (i + 1) * (n - i);
        }
    }
    return ans;
};

2063. 所有子字符串中的元音

题目描述

解法

方法一：枚举贡献

评论