1220. Count the number of vowel sequences

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 lower-case vowel (‘a’, ‘e’, ‘I ‘,’ O ‘, ‘u’) every vowel ‘a’ can only be followed by ‘e’ every vowel ‘e’ can only be followed by ‘a’ or ‘I’ every vowel ‘O’ can only be followed by ‘I’ or ‘u’ every vowel ‘u’ It can only be followed by ‘A’ because the answer is likely to be large, so please return the result after modulo 10^9 + 7.

Example 1

Input: n = 1 Output: 5 Description: All possible strings are: "A "," E ", "I "," O ", and "u".Copy the code

Answer key

Data magnitude 10410^4104; At this magnitude, the last step determines the next step; According to my experience in leetcode, this problem is most likely to use dynamic programming.

When thinking of dynamic programming, state transition equations must be considered.

  • The ‘a’, ‘e’, ‘I’, ‘o’, ‘u’ one by one on the list in the array = [,1,1,1,1 [1]];
  • For any k position
  • The number at the end of a list [k] [0] = list [k – 1] + [1] the list [k – 1] [2] + list [k – 1] [4]
  • List [k][1]= List [k−1][0]+list[k−1][2]
  • List [k][2]= List [k−1][1]+list[k−1][3]
  • O Number of endings List [k][3]=list[k−1][2]
  • List [k][4]= List [k−1][2]+list[k−1][3]

Edit the code according to the above state transition equation as follows

code

var countVowelPermutation = function (n) {
  const MOD = 1000000007
  const list = []
  for (let i = 0; i < n; i++) {
    list[i] = Array(5).fill(0)
  }
  list[0] = Array(5).fill(1)
  for (let i = 1; i < n; i++) {
    list[i][0] = list[i - 1] [0]
    list[i][0] = list[i - 1] [1]
    list[i][1] = list[i - 1] [0] + list[i - 1] [2]
    list[i][2] =
      list[i - 1] [0] + list[i - 1] [1] + list[i - 1] [3] + list[i - 1] [4]
    list[i][3] = list[i - 1] [2] + list[i - 1] [4]
    list[i][4] = list[i - 1] [0]
    for (let j = 0; j < 5; j++) list[i][j] %= MOD
  }
  let result = 0
  for (let i = 0; i < 5; i++) result += list[n - 1][i]
  return result % MOD
}
Copy the code