Sponsored
Sponsored
This approach uses dynamic programming to build up the solution by storing the number of strings of length n ending with each vowel, based on the rules provided. We use a table where each row corresponds to a length from 1 to n, and each column corresponds to a vowel. The value at each cell (i, j) represents the number of strings of length i that end with the respective vowel j.
We update this table iteratively by considering the transition rules from one vowel to another, ensuring only valid transitions contribute to the count. Finally, we sum up the counts for all vowels at length n to get the result.
Time Complexity: O(n), since we iterate through each position up to n.
Space Complexity: O(1), since we only keep track of the current and next states without additional memory usage.
1def count_vowel_permutation(n):
2 MOD = 10**9 + 7
3 # Vowel states initialized
4 dp = [1, 1, 1, 1, 1] # Represents counts for a, e, i, o, u respectively
5 for _ in range(1, n):
6 dp_next = [0] * 5
7 dp_next[0] = (dp[1]) % MOD # a can follow e
8 dp_next[1] = (dp[0] + dp[2]) % MOD # e can follow a, i
9 dp_next[2] = (dp[0] + dp[1] + dp[3] + dp[4]) % MOD # i can follow a, e, o, u
10 dp_next[3] = (dp[2] + dp[4]) % MOD # o can follow i, u
11 dp_next[4] = (dp[0]) % MOD # u can follow a
12 dp = dp_next
13 return sum(dp) % MOD
14
15# Usage:
16# print(count_vowel_permutation(1)) # Output: 5
17# print(count_vowel_permutation(2)) # Output: 10The Python code uses an array to track the number of paths ending with each vowel. In each iteration, a new array 'dp_next' is computed based on the current state of 'dp'. Each array index corresponds to a vowel, and they are updated according to the transition rules given:
After processing n steps, the result is the sum of the counts of strings ending with each vowel, modulo 10^9 + 7.
This approach is similar to the previous one but breaks down the state transitions further into distinct functions, or transitions explicitly defined between states (vowels). It effectively uses a dynamic programming table but emphasizes clear rules defining how counts from one step translate to the next.
Time Complexity: O(n) for calculations across string length iteratively.
Space Complexity: O(1), utilizing a constant array scale unrelated to n.
1#include <iostream>
2#include <vector>
3
4class VowelPermutation {
5public:
int countVowelPermutation(int n) {
const int MOD = 1000000007;
std::vector<long> dp(5, 1); // a, e, i, o, u
for (int i = 1; i < n; ++i) {
std::vector<long> dpNext(5);
dpNext[0] = (dp[1] + dp[2] + dp[4]) % MOD; // a follows e, i, u
dpNext[1] = (dp[0] + dp[2]) % MOD; // e follows a, i
dpNext[2] = (dp[1] + dp[3]) % MOD; // i follows e, o
dpNext[3] = dp[2] % MOD; // o follows i
dpNext[4] = (dp[2] + dp[3]) % MOD; // u follows i, o
dp = dpNext;
}
long sum = 0;
for (long x : dp) sum = (sum + x) % MOD;
return sum;
}
};
int main() {
VowelPermutation vp;
std::cout << vp.countVowelPermutation(1) << std::endl; // Output: 5
std::cout << vp.countVowelPermutation(2) << std::endl; // Output: 10
return 0;
}The C++ code offers a slightly more verbose approach, further clarifying transitions between each vowel index state. Functional decomposition is used by specifying transition rules explicitly for each vowel state, showing how dp[i] evolves into dp[next]. This approach emphasizes clarity of state changes across each step n.