LeetCode 题解工作台
统计字典序元音字符串的数目
给你一个整数 n ，请返回长度为 n 、仅由元音 ( a , e , i , o , u ) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列 需要满足：对于所有有效的 i ， s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。 示例 1： 输入： n =…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $dfs(i, j)$，表示当前已经选了 个元音字母，且最后一个元音字母是 的方案数。那么答案就是 $dfs(0, 0)$。 函数 $dfs(i, j)$ 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数 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
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示当前已经选了 个元音字母，且最后一个元音字母是 的方案数。那么答案就是 。
函数 的计算过程如下：
- 如果 ，说明已经选了 个元音字母，返回 。
- 否则，枚举 后面的元音字母，即 ，并将 的结果累加，即 。
过程中，我们可以使用记忆化搜索，将已经计算过的 的结果保存起来，避免重复计算。
时间复杂度 ，空间复杂度 。其中 为题目给定的整数，而 是元音字母的数量，本题中 。
class Solution:
def countVowelStrings(self, n: int) -> int:
@cache
def dfs(i, j):
return 1 if i >= n else sum(dfs(i + 1, k) for k in range(j, 5))
return dfs(0, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n _k) for DP or O(1) for the combinatorial formula, where k=5 vowels. Space is O(n_ k) for DP or O(1) using combinatorial calculation. The DP approach explicitly demonstrates the state transition pattern for interviews. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks about handling lexicographic constraints efficiently.
- question_mark
Hints at using DP but expects recognition of combinatorial shortcut.
- question_mark
May probe optimization beyond simple DP table.
常见陷阱
外企场景- error
Confusing lexicographic order and strictly increasing order, leading to incorrect counts.
- error
Failing to account for all previous vowel choices in DP transitions.
- error
Trying to generate all strings instead of counting, causing timeouts for large n.
进阶变体
外企场景- arrow_right_alt
Count sorted consonant strings of length n with similar DP approach.
- arrow_right_alt
Compute number of length-n strings with both vowels and consonants sorted.
- arrow_right_alt
Generalize to m distinct characters instead of 5 vowels, maintaining DP state transition.