README.md

1641. 统计字典序元音字符串的数目

English Version

题目描述

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

 

示例 1：

输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：

输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：

输入：n = 33
输出：66045

 

提示：

• 1 <= n <= 50 

解法

a	e	i	o 	u
1	1	1	1	1		n=1
5	4	3	2	1		n=2
15	10	6	3	1		n=3
...						n=...

Python3

class Solution:
    def countVowelStrings(self, n: int) -> int:
        cnt = [1] * 5
        for i in range(2, n + 1):
            for j in range(3, -1, -1):
                cnt[j] += cnt[j + 1]
        return sum(cnt)

Java

class Solution {
    public int countVowelStrings(int n) {
        int[] cnt = new int[5];
        Arrays.fill(cnt, 1);
        for (int i = 2; i <= n; ++i) {
            for (int j = 3; j >= 0; --j) {
                cnt[j] += cnt[j + 1];
            }
        }
        return Arrays.stream(cnt).sum();
    }
}

C++

class Solution {
public:
    int countVowelStrings(int n) {
        vector<int> cnt(5, 1);
        for (int i = 2; i <= n; ++i)
            for (int j = 3; j >= 0; --j)
                cnt[j] += cnt[j + 1];
        return accumulate(cnt.begin(), cnt.end(), 0);
    }
};

Go

func countVowelStrings(n int) int {
	cnt := make([]int, 5)
	for i := range cnt {
		cnt[i] = 1
	}
	for i := 2; i <= n; i++ {
		for j := 3; j >= 0; j-- {
			cnt[j] += cnt[j+1]
		}
	}
	ans := 0
	for _, v := range cnt {
		ans += v
	}
	return ans
}

...