Leetcode.1220 统计元音字母序列的数目

题目链接

Leetcode.1220 统计元音字母序列的数目 Rating ： 1730

题目描述

给你一个整数 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\ast 10^4$

分析：线性dp

按照题目的要求，合法的组合如下：

• 结尾是 a的，ea , ua , ia
• 结尾是 e的，ae , ie
• 结尾是 i的，ei , oi
• 结尾是 o的，io
• 结尾是 u的·，iu , ou

我们定义 $f(i,j)$ 为第 j个字符为 a , e , i , o , u的方案数，$f(1,j)$ 就是第 j个字符为 a的方案数。

按照定义，答案为 $ans=(f(1,n)+f(2,n)+f(3,n)+f(4,n)+f(5,n))modMOD$

时间复杂度： $O(n)$

C++代码：

const int MOD = 1e9 + 7;
using LL = long long;
class Solution {
public:int countVowelPermutation(int n) {LL f[6][n+1];memset(f,0,sizeof f);for(int i = 1;i <= 5;i++) f[i][1] = 1;for(int i = 2;i <= n;i++){//ea , ia , uaf[1][i] = (f[2][i-1] + f[3][i-1] + f[5][i-1]) % MOD;//ae , ief[2][i] = (f[1][i-1] + f[3][i-1]) % MOD;//ei , oif[3][i] = (f[2][i-1] + f[4][i-1]) % MOD;//iof[4][i] = (f[3][i-1]) % MOD;//iu , ouf[5][i] = (f[3][i-1] + f[4][i-1]) % MOD;}LL ans = 0;for(int i = 1;i <= 5;i++) ans = (ans + f[i][n]) % MOD;return ans;}
};

Java代码：

class Solution {private final int MOD = 1000_000_007;public int countVowelPermutation(int n) {long[][] f = new long[6][n + 1];for(int i = 1;i <= 5;i++) f[i][1] = 1;//1->a 2->e 3->i 4->o 5->ufor(int i = 2;i <= n;i++){//ea , ia , uaf[1][i] = (f[2][i-1] + f[3][i-1] + f[5][i-1]) % MOD;//ae , ief[2][i] = (f[1][i-1] + f[3][i-1]) % MOD;//ei , oif[3][i] = (f[2][i-1] + f[4][i-1]) % MOD;//iof[4][i] = (f[3][i-1]) % MOD;//iu , ouf[5][i] = (f[3][i-1] + f[4][i-1]) % MOD;}long ans = 0;for(int i = 1;i <= 5;i++) ans = (ans + f[i][n]) % MOD;return (int)ans;}
}