I prefer orange one
Magic Cursor

力扣每日一题 1641. 统计字典序元音字符串的数目

发布日期：2023-03-29 文章字数：0.6K

1. 题目

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：n = 33
输出：66045

提示：

  • 1 <= n <= 50

2. 思路

2.1. 初步思路

令 0 -> a, 1 -> e, 2 -> i, 3 -> o, 4 -> u
定义数组f[i][j]表示长度为i，以j结尾的字符串的数量

尝试模拟出n=3的情况：

1
2
3
4
5
推导过程：
# n     a   e   i   o   u
# 1     1   1   1   1   1
# 2     5   4   3   2   1
# 3     15  10  6   3   1

可以看出，f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + f[i - 1][j - 2] + f[i - 1][j - 3] + f[i - 1][j - 4]

可以获得初步代码：

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

3. 代码

3.1. 动态规划

1
2
3
4
5
6
7
class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [1] * 5 # 创造一个长度为5的数组，每个元素都是1
        for _ in range(n - 1): # 重复n-1次，每次循环都是在上一次的基础上加上一个元音字母
            for i in range(1, 5): # 从第二个元素开始，每个元素都加上前一个元素的值
                dp[i] += dp[i - 1] # 例如：[1, 1, 1, 1, 1] -> [1, 2, 3, 4, 5]，或是[1, 2, 3, 4, 5] -> [1, 3, 6, 10, 15]
        return sum(dp) # 返回数组的和