所有子字符串中的元音 —— LeetCode - 2063

1. 问题描述：

给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 ‘a’、‘e’、‘i’、‘o’ 和 ‘u’ 。子字符串 是字符串中一个连续（非空）的字符序列。
注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。

2. 示例：

示例 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 个元音。

3. 题解

（1）普通方法（递推公式）

这种方法的核心思想是：从头到尾遍历每一个元音，对每一个元音计算该元音在所有子字符串中出现的次数（不考虑其他位置的元音情况），也就是说，遍历到这个元素时，如果是元音，就计算一共有多少个子字符串含有此元素即可；如果不是元音，则指针直接向右移动，不进行处理。那么，现在只剩下一个问题 —— 如何计算包含某元素的子字符串有几个呢？

决定一个子字符串的只有两个因素，一个是字符串首位置，一个是字符串末位置，因此我们只需要计算针对一个位置，包含该位置的字符串有几种首末位置组合即可。现在问题变得非常简单了，假如 i 是元音，则首位置范围是 0 ~ i ，共 i + 1种选择，末位置范围是 i ~ n - 1，共 n - i 种选择，即包含该元音的字符串数量为（i + 1）* （n - i） .

（2）动态规划DP求解：

我们以上图为例，研究一下DP算法是如何根据子问题自底向上求解问题的。我们引入变量preNum，记录以当前元素为结尾的字符串中含有元音的总个数。这个思想可以参考最大连续子序列和的DP方法，可以参考：https://blog.csdn.net/m0_51339444/article/details/123769968，以上图为例，假如以3为结尾的元音总数为 k ，该子问题（只有3个元素）答案为ans。假如 4 是元音，我们更新一下ans和preNum，preNum的值在原来的基础上增加了4（4个4），而第四个元素索引为3，因此，preNum += i + 1; 再考虑ans , 在原来的基础上增加了4个元素，1234，234，34，4，我们拆开来看，123，23，3和4个4（4就是i + 1）,而123,23,3所含元音总数正是上一个preNum，因此ans += preNum + i + 1;，而边界条件，我们只需要对第一个元素判断一下是否为元音进行相应处理即可。

4. 代码：

（1）方法一：

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

    }
};

（2）方法二：

class Solution {
    
public:
    map<char,int> mp;
    long long countVowels(string word) {
    
        mp['a']=1;mp['e']=1;mp['i']=1;mp['o']=1;mp['u']=1;
        int wrdSize = word.size();
        long long ans = 0;
        long long preNum = 0; //除了后面可能加入的元音外，每一个以当前字母结尾的所有字串的元音总数
        if(mp[word[0]]) {
       // 边界条件
            ans = 1; 
            preNum = 1;
        } 
        for(int i = 1; i < wrdSize ; i++){
    
            if(mp[word[i]]){
    
                ans += preNum + i + 1;
                preNum = preNum + i + 1;
            }
            else ans += preNum;
        }
        return ans;

    }
};