“This is the second day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.
第24 日 2021.1.19
Count the number of vowel sequences
- Leetcode: leetcode-cn.com/problems/co…
- Difficulty: difficulty
- Method: Dynamic programming
The title
- Given an integer n, please count how many strings of length n we can form according to the following rules:
- Every character in a string should be a lowercase vowel (‘a’, ‘e’, ‘I ‘,’ O ‘, ‘u’)
- Every vowel ‘a’ can only be followed by ‘e’
- Each vowel ‘e’ can only be followed by ‘a’ or ‘I’
- Each vowel ‘I’ cannot be followed by another ‘I’
- Each vowel ‘o’ can only be followed by ‘I’ or ‘u’
- Each vowel ‘u’ can only be followed by ‘a’
- Since the answer may be large, return the result after modulo 10^9 + 7.
The sample
- Example 1
Input: n = 1 Output: 5 Description: All possible strings are: "A "," E ", "I "," O ", and "u".Copy the code
- Example 2
Input: n = 2 output: 10: all possible strings are: "ae", "ea", "ei" and "ia" and "ie", "IO", "iu", "oi", "ou" and "ua".Copy the code
- Example 3
Input: n = 5 Output: 68Copy the code
prompt
1 <= n <= 2 * 10^4
solution
Solution 1: Dynamic programming
- How many strings of length N can be formed according to the rules in the problem? In fact, it is necessary to count the vowel letters at the end of the string based on the last one, check the vowel letters that can be matched, and calculate the total number of these vowels.
- In other words: given the number of vowels at the end of the string, we can calculate the total number of vowels that can be matched next time.
- And now thatThe final vowelSo let’s switch the topic
- The preceding trailing letter is
e \ i \ u
Can produce the next ending fora
The string - The preceding trailing letter is
i \ a
Can produce the next ending fore
The string - The preceding trailing letter is
o \ e
Can produce the next ending fori
The string - The preceding trailing letter is
i
Can produce the next ending foro
The string - The preceding trailing letter is
o \ i
Can produce the next ending foru
The string
- The preceding trailing letter is
- Then the dynamic programming equation is:
dp[z][j] = ?
z
Represents: Lengthj
Represents: the last vowel of the current stringdp[z][j]
Indicates the current lengthz
Down, and the end isj
The length of the vowel
- Combined with the above analysis, deduce
dp[z][a] = dp[z - 1][e] + dp[z - 1][i] + dp[z - 1][u]
dp[z][e] = dp[z - 1][i] + dp[z - 1][a]
dp[z][i] = dp[z - 1][e] + dp[z - 1][o]
dp[z][o] = dp[z - 1][i]
dp[z][u] = dp[z - 1][o] + dp[z - 1][i]
- Storing characters can be a little inconvenient, so replace vowel characters with
0,1,2,3,4
To write
/ * * *@param {number} n
* @return {number}* /
var countVowelPermutation = function(n) {
let dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(5).fill(0);
}
// record the modulo value
let mod = 1000000007;
// Initialization: the number of vowel endings when the length is 1
dp[0] [0] = 1;
dp[0] [1] = 1;
dp[0] [2] = 1;
dp[0] [3] = 1;
dp[0] [4] = 1;
for (let i = 1; i < n; i++) {
dp[i][0] = (dp[i - 1] [4] + dp[i - 1] [2] + dp[i - 1] [1]) % mod;
dp[i][1] = (dp[i - 1] [0] + dp[i - 1] [2]) % mod;
dp[i][2] = (dp[i - 1] [1] + dp[i - 1] [3]) % mod;
dp[i][3] = (dp[i - 1] [2]) % mod;
dp[i][4] = (dp[i - 1] [2] + dp[i - 1] [3]) % mod;
}
// console.log('shuchu',dp);
let sum = (dp[n - 1] [0] + dp[n - 1] [1] + dp[n - 1] [2] + dp[n - 1] [3] + dp[n - 1] [4]) % mod;
return sum;
};
Copy the code
- The above solution is feasible, but after submission, it is found that the memory consumption is too large (as shown in the figure below), so the solution is optimized, see solution II below
Solution 2 :(after optimization) dynamic programming
- When thinking about optimization method, found
for
Cycle from2 ~ n
In the traversal of, there is no need to record all the data of each length, only the data of the previous step and the current data are useful, so two constant series groups are used for optimization.
- Optimized complexity
- Time complexity:
O (C (n)
, includingn
Is a given,C
The number of vowels, in this caseC=5
. - Space complexity:
O(C)
, we only need constant space to store the number of different groups.
- Time complexity:
- The code shown
// Optimization: Use two arrays
let dpPre = new Array(5).fill(1);
let dpCur = new Array(5).fill(1);
// Set the modulus value
let mod = 1000000007;
// Loop over the number in the array
for (let i = 2; i <= n; i++) {
dpCur[0] = (dpPre[4] + dpPre[2] + dpPre[1]) % mod;
dpCur[1] = (dpPre[0] + dpPre[2]) % mod;
dpCur[2] = (dpPre[1] + dpPre[3]) % mod;
dpCur[3] = (dpPre[2]) % mod;
dpCur[4] = (dpPre[2] + dpPre[3]) % mod;
dpPre.splice(0.5. dpCur); }return (dpCur[0] + dpCur[1] + dpCur[2] + dpCur[3] + dpCur[4]) % mod;
Copy the code
The appendix
- The topic of dynamic programming still needs more practice, make persistent efforts!