Easy

题目描述

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

元音子串是仅由元音字母（‘a’, ’e’, ‘i’, ‘o’, ‘u’）组成且包含所有五个元音字母的子串。

给定一个字符串 word，返回 word 中元音子串的数量。

示例 1：

输入：word = "aeiouu"
输出：2
解释：word 的元音子串如下（加下划线的）：
- "aeiouu"
- "aeiouu"

示例 2：

输入：word = "unicornarihan"
输出：0
解释：没有包含所有 5 个元音字母，因此没有元音子串。

示例 3：

输入：word = "cuaieuouac"
输出：7
解释：word 的元音子串如下（加下划线的）：
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

约束条件：

  • 1 <= word.length <= 100
  • word 仅由小写英文字母组成

提示：

  • 在生成从任何索引开始的子串时，如果遇到辅音字母，你还需要继续生成更大的子串吗？
  • 你可以存储字符计数来完全避免生成子串吗？

解题思路

解题思路

这道题要求统计包含所有五个元音字母且仅由元音字母组成的子串数量。

核心思路：

  1. 双指针枚举： 对于每个起始位置，向右扩展寻找所有可能的元音子串
  2. 早期终止： 一旦遇到辅音字母，立即停止当前起始位置的搜索
  3. 计数优化： 使用计数数组记录当前窗口中每个元音字母的出现次数

具体算法：

  • 外层循环确定子串的起始位置
  • 内层循环从起始位置向右扩展
  • 使用长度为5的计数数组记录当前窗口中五个元音字母的数量
  • 当遇到非元音字母时，立即break
  • 当所有五个元音字母都至少出现一次时，该子串有效，计数器加1

时间复杂度优化： 虽然看起来是O(n²)，但由于字符串长度限制在100以内，且遇到辅音会提前终止，实际运行效率很高。

这种方法既简洁又高效，是该题的最优解法。

代码实现

class Solution {
public:
    int countVowelSubstrings(string word) {
        int n = word.length();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            vector<int> vowelCount(5, 0);
            for (int j = i; j < n; j++) {
                char c = word[j];
                
                if (c == 'a') vowelCount[0]++;
                else if (c == 'e') vowelCount[1]++;
                else if (c == 'i') vowelCount[2]++;
                else if (c == 'o') vowelCount[3]++;
                else if (c == 'u') vowelCount[4]++;
                else break;
                
                if (vowelCount[0] > 0 && vowelCount[1] > 0 && 
                    vowelCount[2] > 0 && vowelCount[3] > 0 && vowelCount[4] > 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        n = len(word)
        count = 0
        
        for i in range(n):
            vowel_count = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
            for j in range(i, n):
                c = word[j]
                
                if c in vowel_count:
                    vowel_count[c] += 1
                else:
                    break
                
                if all(count > 0 for count in vowel_count.values()):
                    count += 1
        
        return count

public class Solution {
    public int CountVowelSubstrings(string word) {
        int n = word.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int[] vowelCount = new int[5];
            for (int j = i; j < n; j++) {
                char c = word[j];
                
                if (c == 'a') vowelCount[0]++;
                else if (c == 'e') vowelCount[1]++;
                else if (c == 'i') vowelCount[2]++;
                else if (c == 'o') vowelCount[3]++;
                else if (c == 'u') vowelCount[4]++;
                else break;
                
                if (vowelCount[0] > 0 && vowelCount[1] > 0 && 
                    vowelCount[2] > 0 && vowelCount[3] > 0 && vowelCount[4] > 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var countVowelSubstrings = function(word) {
    const n = word.length;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        const vowelCount = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0};
        for (let j = i; j < n; j++) {
            const c = word[j];
            
            if (c in vowelCount) {
                vowelCount[c]++;
            } else {
                break;
            }
            
            if (Object.values(vowelCount).every(count => count > 0)) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²)，其中 n 是字符串长度。最坏情况下需要检查所有可能的子串，但遇到辅音字母会提前终止
空间复杂度O(1)，只使用了固定大小的计数数组来存储五个元音字母的出现次数

相关题目