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

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

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

思路

简单动态规划，每一次加字符都遍历一次元音字母，当前位数出现的总数为上一次遍历中可以组成合法字符串的数量之和：a 之前的有 ea、ia、ua 。e 之前的只有 ae、ie。i 之前的只有 ei、oi。o 之前的有 io。u 之前的有 iu、ou。最后统计 dp 数组的和即可。

解答

/**
 * @param {number} n
 * @return {number}
 */
var countVowelPermutation = function (n) {
  const mod = 10 ** 9 + 7;
  const dp = [1, 1, 1, 1, 1];
  while (n > 1) {
    const temp = dp.slice();
    // ea ia ua
    temp[0] = (dp[1] + dp[2] + dp[4]) % mod;
    // ae ie
    temp[1] = (dp[0] + dp[2]) % mod;
    // ei oi
    temp[2] = (dp[1] + dp[3]) % mod;
    // io
    temp[3] = dp[2] % mod;
    // iu ou
    temp[4] = (dp[2] + dp[3]) % mod;
    dp.splice(0, 5, ...temp);
    n--;
  }
  return dp.reduce((a, b) => (a + b) % mod);
};