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: 68

Constraints:
1 <= n <= 2*10^4

Hints:
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:
Summits set epoch-making milestone in history of China-Arab ties
In the face of COVID-19 pandemic, China and Arab countries have
15 Macao residents qualify as candidates for deputies to nationa
Study finds genetic solution to pre-harvest sprouting in rice, w
Bodybuilders dying as coaches, judges encourage extreme measures
Malta's Marsaskala, China's Dujiangyan sign sister city agreemen
U.S. mortgage applications continue slide amid surging interest
Russian, UAE presidents discuss bilateral cooperation over phone
Hate crimes in U.S. Los Angeles County rise to highest level sin
Chinese mainland reports 4,031 new local confirmed COVID-19 case
Share:Facebook Twitter
Comment list
Comment add