README.md

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

English Version

题目描述

给你一个整数 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 [e]
e [a|i]
i [a|e|o|u]
o [i|u]
u [a]

=>

[e|i|u]	a
[a|i]	e
[e|o]	i
[i]	o
[i|o]	u

设 $dp[i][j]$ 表示当前长度为 $i$ 且以字符 j 为结尾的字符串的数目，其中 j = {0,1,2,3,4} 分别代表元音字母 a,e,i,o,u。

Python3

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = (1, 1, 1, 1, 1)
        MOD = 1000000007
        for _ in range(n - 1):
            dp = (
                (dp[1] + dp[2] + dp[4]) % MOD,
                (dp[0] + dp[2]) % MOD,
                (dp[1] + dp[3]) % MOD,
                dp[2],
                (dp[2] + dp[3]) % MOD,
            )
        return sum(dp) % MOD

Java

class Solution {
    private static final long MOD = (long) 1e9 + 7;

    public int countVowelPermutation(int n) {
        long[] dp = new long[5];
        long[] t = new long[5];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n - 1; ++i) {
            t[0] = (dp[1] + dp[2] + dp[4]) % MOD;
            t[1] = (dp[0] + dp[2]) % MOD;
            t[2] = (dp[1] + dp[3]) % MOD;
            t[3] = dp[2];
            t[4] = (dp[2] + dp[3]) % MOD;
            System.arraycopy(t, 0, dp, 0, 5);
        }
        long ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans = (ans + dp[i]) % MOD;
        }
        return (int) ans;
    }
}

C++

class Solution {
public:
    int countVowelPermutation(int n) {
        using ll = long long;
        const ll mod = 1e9 + 7;
        vector<ll> dp(5, 1);
        vector<ll> t(5);
        for (int i = 0; i < n - 1; ++i) {
            t[0] = (dp[1] + dp[2] + dp[4]) % mod;
            t[1] = (dp[0] + dp[2]) % mod;
            t[2] = (dp[1] + dp[3]) % mod;
            t[3] = dp[2];
            t[4] = (dp[2] + dp[3]) % mod;
            dp = t;
        }
        return accumulate(dp.begin(), dp.end(), 0LL) % mod;
    }
};

Go

func countVowelPermutation(n int) int {
	const mod int = 1e9 + 7
	dp := [5]int{1, 1, 1, 1, 1}
	for i := 0; i < n-1; i++ {
		dp = [5]int{
			(dp[1] + dp[2] + dp[4]) % mod,
			(dp[0] + dp[2]) % mod,
			(dp[1] + dp[3]) % mod,
			dp[2],
			(dp[2] + dp[3]) % mod,
		}
	}
	ans := 0
	for _, v := range dp {
		ans = (ans + v) % mod
	}
	return ans
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var countVowelPermutation = function (n) {
    const mod = 1000000007;
    const dp = new Array(5).fill(1);
    const t = new Array(5).fill(0);
    for (let i = 0; i < n - 1; ++i) {
        t[0] = (dp[1] + dp[2] + dp[4]) % mod;
        t[1] = (dp[0] + dp[2]) % mod;
        t[2] = (dp[1] + dp[3]) % mod;
        t[3] = dp[2];
        t[4] = (dp[2] + dp[3]) % mod;
        dp.splice(0, 5, ...t);
    }
    let ans = 0;
    for (let i = 0; i < 5; ++i) {
        ans = (ans + dp[i]) % mod;
    }
    return ans;
};

...