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

发表于： 2024-03-05 分类于： leetcode

字数： 1024 阅读：≈ 3分钟

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

给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。

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

**注意：**由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。

思路

基本思想

本题有四种解题思路：

暴力：依次从word的每一个位置向后出发，然后统计每一个字符串中的元音个数累加，这种方式从word的每一个位置向后出发时有很多重复统计工作造成超时：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    //不停地从新的位置向后扩张，直到走到最后
    //每获得一个子字符串就计算元音个数，然后累加到结果中
    long res=0;
    public long countVowels(String word) {
        Set<Character> set=new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        char[] ch=word.toCharArray();
        for(int i=0;i<ch.length;++i){
            int num=0;
            for(int j=i;j<ch.length;++j){
                //当前子字符串出现元音就开始统计
                if(set.contains(ch[j])){
                    ++num;
                }
                //每个子字符串中的元音个数都需要累加到res中
                res+=num;
            }
        }
        return res;
    }
}

递归：依次从word的每一个位置向后递归，每递归到一个位置就统计当前位置形成的子字符串的元音个数，也会超时：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    //不停地从新的位置向后扩张，直到走到最后
    //每获得一个子字符串就计算元音个数，然后累加到结果中
    //这样做会超时
    long res=0;
    Set<Character> set=new HashSet<>();
    public long countVowels(String word) {
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        char[] ch=word.toCharArray();
        for(int i=0;i<ch.length;++i){
            help(ch,i,0);
        }
        return res;
    }
    public void help(char[] ch,int index,int num){
        if(index==ch.length)
            return;
        //当前位置是元音，当前子字符串元音个数+1
        if(set.contains(ch[index]))
            ++num;
        res+=num;
        help(ch,index+1,num);
    }
}

从中间统计：以word的每一个位置i为中点，前面的i+1个元素依次带上后面的length-i个元素都可以形成带有元音字母的子字符串了，例如xyzabcdf中的a所处位置为3，依次从前面4（3+1）个位置为起点，然后以后面5（8-3）个位置为终点形成的子字符串都带有元音字母a，就这样依次统计即可：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Solution {
    private long sum = 0;
    public long countVowels(String word) {
        Set<Character> set=new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        for (int i = 0; i < word.length(); i++) {
            if (set.contains(word.charAt(i))) {
                sum += (i + 1)*(word.length()-i);
            } 
        }
        return sum;
    }
}

动态规划：dp[i+1]代表以i结尾的所有子字符串包含的元音个数，如果当前位置i是元音字母，那么动态规划方程为： $$ dp[i+1]=dp[i]+i+1 $$ 其中加上i+1代表以i结尾可以形成i+1个子字符串，这些子字符串都带有元音，更新之后累加即可，观察出dp只与前一个位置有关，所以dp可以简化成一个变量：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    private long dp = 0;
    private long sum = 0;
    public long countVowels(String word) {
        Set<Character> set=new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        for (int i = 0; i < word.length(); i++) {
            if (set.contains(word.charAt(i))) {
                dp += (i + 1);
            } 
            sum += dp;
        }
        return sum;
    }
}

总结

主要是要能从暴力法中简化出新的解题方法，去掉很多无用的工作