跳转至

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

问题描述#

给你一个整数 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 

解题思路#

循环计算前缀和。

1
2
3
4
5
6
7
     以该字母开头的字符串数量
   |  u   o   i   e   a   |
---|----------------------|------
#1 |  1   1   1   1   1   |  5
#2 |  1   2   3   4   5   |  15
#3 |  1   3   6   10  15  |  35
#4 |  1   4   10  20  35  |  70

1
2
3
4
5
6
7
8
class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [1] * 5

        for _ in range(n - 1):
            for i in range(1, 5):
                dp[i] += dp[i - 1]
        return sum(dp)
返回顶部

在手机上阅读