跳转至

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

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、解题思路

  • 这道题当前状态只跟前一个状态相关,长度少一的相关,这里只有5种情况,直接计算即可
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod_num = 1000000007
        step = 1
        pre = [1] * 5
        temp = [0] * 5
        while step < n:
            temp[0] += pre[1] % mod_num
            temp[1] += (pre[0] + pre[2]) % mod_num
            temp[2] += (sum(pre) - pre[2]) % mod_num
            temp[3] += (pre[2] + pre[4]) % mod_num
            temp[4] += pre[0]

            pre = temp
            temp = [0] * 5
            step += 1
        return sum(pre) % mod_num