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

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

字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）

每个元音 'a' 后面都只能跟着 'e'

每个元音 'e' 后面只能跟着 'a' 或者是 'i'

每个元音 'i' 后面不能再跟着另一个 'i'

每个元音 'o' 后面只能跟着 'i' 或者是 'u'

每个元音 'u' 后面只能跟着 'a'

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

(https://leetcode-cn.com/problems/count-vowels-permutation/)

示例

示例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

思路

计算每次以不同字母结尾的数量

源码

function countVowelPermutation(n: number): number {
    //数组tail保存以5个元音字母结尾的字符串数
    //a=u+i+e,e=a+i,i=e+o,o=i,u=o+i
    const M=1e9+7;
    let tail=[1,1,1,1,1],temp=new Array(5);
    for(let i=0;i<n-1;i++){
        temp = [0, 0, 0, 0, 0];
        temp[0] = (tail[1] + tail[2] + tail[4])%M;
        temp[1] = (tail[0] + tail[2])%M;
        temp[2] = (tail[1] + tail[3])%M;
        temp[3] = tail[2]%M;
        temp[4] = (tail[2] + tail[3])%M;
        tail = temp;
    }
    return (tail[0]+tail[1]+tail[2]+tail[3]+tail[4])%M;
};