Dynamic Programming Algorithm to Count Vowels Permutation
- Time:2020-09-11 08:17:29
- Class:Weblog
- Read:31
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: 68Constraints:
1 <= n <= 2*10^4Hints:
Use dynamic programming.
Let dp[i][j] be the number of strings of length i that ends with the j-th vowel.
Deduce the recurrence from the given relations between vowels.
Counting the Vowel Permutation using Dynamic Programming Algorithm
Let’s define d[i][j] a two dimension array (or vector) that stores the count for length i and end with the j-th vowel. Thus, the j is ranged from 0 to 4 – for [‘a’, ‘e’, ‘i’, ‘o’, ‘u’].
The initial values can be set for single vowel, which is dp[1][0..4] = 1. Then, we can loop from size 2 to n, then, based on the rules, only summing up those valid permutations.
The answer may be large, thus we need to apply the MOD operator to the intermediate values.
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 | class Solution { public: int countVowelPermutation(int n) { vector<vector<int64_t>> dp(n + 1, vector<int64_t>(5, 0)); for (int i = 0; i < 5; ++ i) { dp[1][i] = 1; } const int MOD = 1000000007; for (int i = 2; i <= n; ++ i) { dp[i][0] = (dp[i - 1][1] + // ea dp[i - 1][2] + // ia dp[i - 1][4]) % MOD; // ua dp[i][1] = (dp[i - 1][0] + // ae dp[i - 1][2]) % MOD; // ie dp[i][2] = (dp[i - 1][1] + // ei dp[i - 1][3]) % MOD; // oi dp[i][3] = dp[i - 1][2]; // io dp[i][4] = (dp[i - 1][2] + // iu dp[i - 1][3]) % MOD; // ou } return (dp.back()[0] + dp.back()[1] + dp.back()[2] + dp.back()[3] + dp.back()[4]) % MOD; } }; |
class Solution { public: int countVowelPermutation(int n) { vector<vector<int64_t>> dp(n + 1, vector<int64_t>(5, 0)); for (int i = 0; i < 5; ++ i) { dp[1][i] = 1; } const int MOD = 1000000007; for (int i = 2; i <= n; ++ i) { dp[i][0] = (dp[i - 1][1] + // ea dp[i - 1][2] + // ia dp[i - 1][4]) % MOD; // ua dp[i][1] = (dp[i - 1][0] + // ae dp[i - 1][2]) % MOD; // ie dp[i][2] = (dp[i - 1][1] + // ei dp[i - 1][3]) % MOD; // oi dp[i][3] = dp[i - 1][2]; // io dp[i][4] = (dp[i - 1][2] + // iu dp[i - 1][3]) % MOD; // ou } return (dp.back()[0] + dp.back()[1] + dp.back()[2] + dp.back()[3] + dp.back()[4]) % MOD; } };
The final solution will be the sum for the 5 values in dp[n][0..4]. Complexity: O(N) time and O(N) space.
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:How to Construct Binary Search Tree from Preorder Traversal in P
Dynamic Programming Algorithm to Compute the Block Sum in a Matr
Smallest Multiple Algorithm using Bruteforce or GCD/LCM
How many different ways can £2 be made using any number of coins
Compute Factorial Digit Sum: Find the sum of the digits in the n
Compute the Maximum Integer Right Triangles Solutions
Power Digit Sum: What is the sum of the digits of the number 2^1
Digit factorials: Find the Sum of All the Curious Numbers
Computing the Longest Recurring Cycle in its Decimal Fraction Pa
How to Use Priority Queue in Java or C++ to Compute Last Stone W
- Comment list
-
- Comment add