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

• 标签：数学、动态规划、组合数学
• 难度：中等

题目链接

• 1641. 统计字典序元音字符串的数目 - 力扣

题目大意

描述：给定一个整数 $n$。

要求：返回长度为 $n$、仅由原音（$a$、$e$、$i$、$o$、$u$）组成且按字典序排序的字符串数量。

说明：

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

示例：

• 示例 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' 靠后

解题思路

思路 1：组和数学

题目要求按照字典序排列，则如果确定了每个元音的出现次数可以确定一个序列。

对于长度为 $n$ 的序列，$a$、$e$、$i$、$o$、$u$ 出现次数加起来为 $n$ 次，且顺序为 $a…a \rightarrow e…e \rightarrow i…i \rightarrow o…o \rightarrow u…u$。

我们可以看作是将 $n$ 分隔成了 $5$ 份，每一份对应一个原音字母的数量。

我们可以使用「隔板法」的方式，看作有 $n$ 个球，$4$ 个板子，将 $n$ 个球分隔成 $5$ 份。

则一共有 $n + 4$ 个位置可以放板子，总共需要放 $4$ 个板子，则答案为 $C_{n + 4}^4$，其中 $C$ 为组和数。

思路 1：代码

class Solution:
    def countVowelStrings(self, n: int) -> int:
        return comb(n + 4, 4)

思路 1：复杂度分析

• 时间复杂度：$O(| \sum |)$，其中 $\sum$ 为字符集，本题中 $| \sum | = 5$ 。
• 空间复杂度：$O(1)$。