原文链接: https://leetcode-cn.com/problems/vowels-of-all-substrings

英文原文

Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word.

A substring is a contiguous (non-empty) sequence of characters within a string.

Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

 

Example 1:

Input: word = "aba"
Output: 6
Explanation: 
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6. 

Example 2:

Input: word = "abc"
Output: 3
Explanation: 
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3. 

Example 3:

Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".

Example 4:

Input: word = "noosabasboosa"
Output: 237
Explanation: There are a total of 237 vowels in all the substrings.

 

Constraints:

• 1 <= word.length <= 105
• word consists of lowercase English letters.

中文题目

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

通过代码

高赞题解

遍历 $\textit{word}$，若 $\textit{word}[i]$ 是元音，我们考察它能出现在多少个子字符串中。

设 $\textit{word}$ 的长度为 $n$。子字符串 $\textit{word}[l..r]$ 若要包含 $\textit{word}[i]$，则必须满足

• $0\le l\le i$
• $i\le r\le n-1$

这样的 $l$ 有 $i+1$ 个，$r$ 有 $n-i$ 个，因此有 $(i+1)(n-i)$ 个子字符串，所以 $\textit{word}[i]$ 在所有子字符串中一共出现了 $(i+1)(n-i)$ 次。

累加所有出现次数即为答案。

func countVowels(word string) (ans int64) {
	for i, ch := range word {
		if strings.ContainsRune("aeiou", ch) {
			ans += int64(i+1) * int64(len(word)-i)
		}
	}
	return
}

统计信息

通过次数	提交次数	AC比率
3987	8317	47.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言