README_EN.md

1220. Count Vowels Permutation

中文文档

Description

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

• Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
• Each vowel 'a' may only be followed by an 'e'.
• Each vowel 'e' may only be followed by an 'a' or an 'i'.
• Each vowel 'i' may not be followed by another 'i'.
• Each vowel 'o' may only be followed by an 'i' or a 'u'.
• Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

 

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3: 

Input: n = 5
Output: 68

 

Constraints:

• 1 <= n <= 2 * 10^4

Solutions

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

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;
};

...