跳到主要内容

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

· 阅读需 4 分钟

1、题干​

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

2、解题思路​

根据题意可以列举出 字符串长度跟结果数的关系 ：

  • 1个字母时只有5种情况："a", "e", "i" , "o" , "u"
  • 2个字母时有10种情况："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" , "ua"

实际上 结果数就是尾字母的个数 ：

  • 1个字母时尾字母个数："a" * 1, "e" * 1, "i" * 1 , "o" * 1 , "u" * 1，总数为5
  • 2个字母时尾字母个数："a" * 3, "e" * 2, "i" * 2 , "o" * 1 , "u" * 2，总数为10

因此，使用数组 c 按字典序存储尾字母 "a", "e", "i" , "o" , "u" 的数量，然后根据题中给出的字母组合关系，可以推导出下一轮的尾字母数量 nc : nc = [c[1] + c[2] + c[4], c[0] + c[2], c[1] + c[3], c[2], c[2] + c[3]]


根据递推公式计算出2个字符以内的情况符合正确结果：

  • 1个字母时尾字母个数为：[1, 1, 1, 1, 1]
  • 2个字母时尾字母个数为：[3, 2, 2, 1, 2]

3、代码​

var countVowelPermutation = function (n) {
    const MOD = 1e9 + 7;
    let c = [1, 1, 1, 1, 1];

    for (let i = 2; i <= n; i++) {
        c = [(c[1] + c[2] + c[4]) % MOD, (c[0] + c[2]) % MOD, (c[1] + c[3]) % MOD, c[2] % MOD, (c[2] + c[3]) % MOD];
    }

    return c.reduce((a, k) => a + k, 0) % MOD;
};

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png