2022-1-17 LeetCode 每日一题 No.1220 统计元音字母序列的数目

原贴地址：https://dawnmagnet.github.io/algorithm-station/docs/2022/1/17

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/count-vowels-permutation著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

本道题其实就是一个找规律分析题，科学一点的讲法叫做动态规划，但真的挺简单的。

根据题目中的意思，我们可以看出，题目所谓的“元音字母序列”实际上就是只跟最后一位字母有关系，也就是说，对于一个序列，我们压根没必要知道它前面是啥，只要告诉我们最后一位字母是啥，就可以继续往下进行扩展了。在这种条件下，我们可以只使用一个数组，保存序列末尾分别对应 aeiou 时的序列数量，就能大大简化计算。

然后根据题目中的条件，自行推导一下，可以发现

• a 前面可以是 eiu

• e 前面可以是 ai

• i 前面可以是 eo

• o 前面可以是 i

• u 前面可以是 io

根据这个条件，就可以实现递推式

在计算出来指定的那一步 aeiou 结尾的序列分别有多少个之后，再对其进行一个简单的相加就可以获得答案。

Rust 代码

const m: i64 = 1_000_000_007;impl Solution {    pub fn count_vowel_permutation(n: i32) -> i32 {        let mut c = [1i64, 1, 1, 1, 1];        for i in 1..n {            c = [                (c[1] + c[2] + c[4]) % m,                (c[0] + c[2]) % m,                (c[1] + c[3]) % m,                c[2],                (c[2] + c[3]) % m,            ];        }        (c.iter().sum::<i64>() % m) as i32    }}