describe

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].	
Copy the code

Example 2:

Input: n = 2 Output: 15 Explanation: The 15 sorted strings that consist of vowels only are ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Note that "ea" is not a valid string since  'e' comes after 'a' in the alphabet.Copy the code

Example 3:

Input: n = 33
Output: 66045
Copy the code

Note:

1 <= n <= 50 
Copy the code

parsing

When n = 1, the number of legal strings that begin with each vowel sound can be listed as follows:

	a e i o u
	1 1 1 1 1
	
Copy the code

When n is 2, it can be listed as follows:

	a e i o u
	1 1 1 1 1
	5 4 3 2 1
Copy the code

When n is 3, it can be listed as follows:

	a e i o u
	1  1  1  1  1
	5  4  3  2  1
	15 10 6  3  1
	
Copy the code

Initialize an array res with five elements, each of which corresponds to the legal number of occurrences of a string beginning with five vowels, res[1] representing legal characters beginning with a bold character, and so on. Traversal n times, each traversal only needs to change res[j] to sum(res[j:]), at the end of the traversal, sum(res) can be obtained.

answer

class Solution(object): def countVowelStrings(self, n): """ :type n: int :rtype: Int "" res = [1,1,1,1] for I in range(1, n): for j in range(5): res[j] = sum(res[j:]) return sum(res)Copy the code

The results

Given in the Python online submissions for Count Sorted Vowel Strings. Sorted Vowel Strings for the Python online submissions for Count.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation