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
Related Topics:
Dynamic Programming
Given the rule, the valid combinations are as follows:
a: ae
e: ea ei
i: ia ie io iu
o: oi ou
u: ua
Let dp[i][j] be the count of valid strings of length i ending with letter j where 0 < i <= n, j = 'a', 'e', 'i', 'o', 'u'.
So we have
dp[i]['a'] = dp[i - 1]['e'] + dp[i - 1]['i'] + dp[i - 1]['u']
dp[i]['e'] = dp[i - 1]['a'] + dp[i - 1]['i']
dp[i]['i'] = dp[i - 1]['e'] + dp[i - 1]['o']
dp[i]['o'] = dp[i - 1]['i']
dp[i]['u'] = dp[i - 1]['i'] + dp[i - 1]['o']
dp[1][j] = 1
The answer is Sum{ dp[n][j] | j = 'a', 'e', 'i', 'o', 'u' }.
// OJ: https://leetcode.com/problems/count-vowels-permutation/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int countVowelPermutation(int n) {
int mod = 1e9 + 7, a = 1, e = 1, i = 1, o = 1, u = 1;
while (--n) {
int aa = ((e + i) % mod + u) % mod;
int ee = (a + i) % mod;
int ii = (e + o) % mod;
int oo = i;
int uu = (i + o) % mod;
a = aa, e = ee, i = ii, o = oo, u = uu;
}
return ((((a + e) % mod + i) % mod + o) % mod + u) % mod;
}
};