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
Solution: DP
dp[i][c] := number of strings of length i ends with letter c
transition: follow the definition
ans = sum(dp[n])
Time complexity: O(n)
Space complexity: O(n) -> O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua class Solution { public: int countVowelPermutation(int n) { constexpr int kMod = 1e9 + 7; vector<vector<long>> dp(n + 1, vector<long>(5)); fill(begin(dp[1]), end(dp[1]), 1); // 0: a, 1: e, 2: i, 3: o, 4: u for (int i = 2; i <= n; ++i) { dp[i][1] += dp[i - 1][0]; // a -> e dp[i][0] += dp[i - 1][1]; // e -> a dp[i][2] += dp[i - 1][1]; // e -> i for (int j = 0; j < 5; ++j) { if (j == 2) continue; dp[i][j] += dp[i - 1][2]; // i -> * } dp[i][2] += dp[i - 1][3]; // o -> i dp[i][4] += dp[i - 1][3]; // o -> u dp[i][0] += dp[i - 1][4]; // u -> a for (int j = 0; j < 5; ++j) dp[i][j] %= kMod; } return accumulate(begin(dp[n]), end(dp[n]), 0L) % kMod; } }; |
C++/O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int countVowelPermutation(int n) { constexpr int kMod = 1e9 + 7; long a = 1, e = 1, i = 1, o = 1, u = 1; for (int k = 2; k <= n; ++k) { long aa = (i + e + u) % kMod; long ee = (i + a) % kMod; long ii = (e + o) % kMod; long oo = i % kMod; long uu = (i + o) % kMod; a = aa; e = ee; i = ii; o = oo; u = uu; } return (a + e + i + o + u) % kMod; } }; |
Solution 2: Matrix multiplication
Time complexity: O(logn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
// Author: Huahua constexpr int kMod = 1e9 + 7; vector<vector<long>> operator*(const vector<vector<long>>& A, const vector<vector<long>>& B) { int m = A.size(); int x = A[0].size(); int n = B[0].size(); vector<vector<long>> C(m, vector<long>(n)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { for (int k = 0; k < x; ++k) C[i][j] += A[i][k] * B[k][j]; C[i][j] %= kMod; } return C; } class Solution { public: int countVowelPermutation(int n) { vector<vector<long>> m{ {0, 1, 0, 0, 0}, // a {1, 0, 1, 0, 0}, // e {1, 1, 0, 1, 1}, // i {0, 0, 1, 0, 1}, // o {1, 0, 0, 0, 0} // u }; vector<vector<long>> ans{{1}, {1}, {1}, {1}, {1}}; n -= 1; while (n > 0) { if (n % 2) ans = m * ans; m = m * m; n /= 2; } long sum = 0; for (int i = 0; i < 5; ++i) sum += ans[i][0]; return sum % kMod; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment