“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 ise \ i \ u Can produce the next ending foraThe string
    • The preceding trailing letter isi \ a Can produce the next ending foreThe string
    • The preceding trailing letter iso \ e Can produce the next ending foriThe string
    • The preceding trailing letter isiCan produce the next ending foroThe string
    • The preceding trailing letter iso \ iCan produce the next ending foruThe string
  • Then the dynamic programming equation is:dp[z][j] = ?
    • zRepresents: Length
    • jRepresents: the last vowel of the current string
    • dp[z][j]Indicates the current lengthzDown, and the end isjThe 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 with0,1,2,3,4To 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, foundforCycle from2 ~ nIn 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), includingnIs a given,CThe number of vowels, in this caseC=5.
    • Space complexity:O(C), we only need constant space to store the number of different groups.
  • 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!