What is the main pattern in Count Vowels Permutation?

The core pattern is state transition dynamic programming, where each vowel can follow only specific previous vowels.

Why do we use modulo 10^9 + 7 in this problem?

The count grows exponentially with n, so modulo prevents integer overflow and keeps calculations manageable.

Can we optimize space in this problem?

Yes, by storing only the counts for the previous length instead of a full DP table, reducing space to O(5).

What is a common mistake when implementing DP for this problem?

Allowing forbidden transitions, such as 'i' followed by 'i', or forgetting modulo at each step.

How do initial values affect the DP approach?

Each vowel at length 1 starts with a count of 1, which seeds the DP iteration correctly.

#1220

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计元音字母序列的数目

给你一个整数 n ，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：字符串中的每个字符都应当是小写元音字母（ 'a' , 'e' , 'i' , 'o' , 'u' ）每个元音 'a' 后面都只能跟着 'e' 每个元音 'e' 后面只能跟着 'a' 或者是 'i' 每个元音 '…

动态规划

题目描述

给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
每个元音 'a' 后面都只能跟着 'e'
每个元音 'e' 后面只能跟着 'a' 或者是 'i'
每个元音 'i' 后面不能再跟着另一个 'i'
每个元音 'o' 后面只能跟着 'i' 或者是 'u'
每个元音 'u' 后面只能跟着 'a'

由于答案可能会很大，所以请你返回模 10^9 + 7 之后的结果。

示例 1：

输入：n = 1
输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。

示例 2：

输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。

示例 3：

输入：n = 5
输出：68

提示：

1 <= n <= 2 * 10^4

lightbulb

解题思路

方法一：动态规划

根据题目描述，我们先列出每个元音字母的后一个字母：

a [e]
e [a|i]
i [a|e|o|u]
o [i|u]
u [a]

那么我们可以推出每个元音字母的前一个字母：

[e|i|u]	a
[a|i]	e
[e|o]	i
[i]	o
[i|o]	u

我们定义 $f[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数，如果长度为 $1$ ，那么 $f[i]=1$ 。

当长度大于 $1$ 时，我们定义 $g[i]$ 表示当前长度以第 $i$ 个元音字母结尾的字符串的个数，那么 $g[i]$ 可以由 $f$ 转移而来，即：

g[i]= \begin{cases} f[1]+f[2]+f[4] & i=0 \\ f[0]+f[2] & i=1 \\ f[1]+f[3] & i=2 \\ f[2] & i=3 \\ f[2]+f[3] & i=4 \end{cases}

最终答案为 $\sum_{i=0}^{4}f[i]$ 。注意由于答案可能会很大，所以需要对 $10^9+7$ 取模。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ 。其中 $n$ 是字符串的长度，而 $C$ 是元音字母的个数。本题中 $C=5$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        f = [1] * 5
        mod = 10**9 + 7
        for _ in range(n - 1):
            g = [0] * 5
            g[0] = (f[1] + f[2] + f[4]) % mod
            g[1] = (f[0] + f[2]) % mod
            g[2] = (f[1] + f[3]) % mod
            g[3] = f[2]
            g[4] = (f[2] + f[3]) % mod
            f = g
        return sum(f) % mod

speed

复杂度分析

指标	值
时间	complexity is O(n) since each step updates 5 states. Space complexity is O(5) with optimized DP, or O(n*5) with a full DP table. Both are efficient for n up to 20,000.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on optimizing space while maintaining correct vowel transitions.
question_mark
Check for off-by-one errors when applying state transitions.
question_mark
Be ready to explain why modulo 10^9 + 7 is required for large n.

warning

常见陷阱

外企场景

error
Incorrectly allowing forbidden transitions like 'i' followed by 'i'.
error
Forgetting to apply modulo after each sum operation, leading to overflow.
error
Using a full DP table without space optimization for large n, wasting memory.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count consonant permutations with custom transition rules.
arrow_right_alt
Allow cyclic transitions and compute permutations with modified DP.
arrow_right_alt
Extend to strings including both vowels and consonants under state rules.

help

常见问题

外企场景

继续练习

#1218 最长定差子序列 #1223 掷骰子模拟 #1227 飞机座位分配概率