LeetCode 1641. Count the number of Lexicographic vowel strings

1641. Count the number of vowel strings in the dictionary

Give you an integer n, Please return the length of n 、 Only by vowels (a, e, i, o, u) Composed and in accordance with Dictionary order The number of strings .

character string s Press Dictionary order Need to meet ： For all that works i,s[i] The position in the alphabet is always the same as s[i+1] Same or in s[i+1] Before .

Example 1：

 Input ：n = 1
 Output ：5
 explain ： Consisting of only vowels  5  Dictionary order strings are  ["a","e","i","o","u"]

Example 2：

 Input ：n = 2
 Output ：15
 explain ： Consisting of only vowels  15  Dictionary order strings are 
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
 Be careful ,"ea"  It's not a string according to the meaning of the question , because  'e'  Position in the alphabet than  'a'  be in the rear 

Example 3：

 Input ：n = 33
 Output ：66045

Tips ：

• 1 <= n <= 50

Two 、 Method 1

Dynamic gauge , Completely backpack

class Solution {
    
    public int countVowelStrings(int n) {
    
        int[] dp = new int[6];
        for (int i = 1; i <= 5; i++) {
    
            dp[i] = 1;
        }
        for (int j = 2; j <= n; j++) {
    
            for (int i = 2; i <= 5; i++) {
    
                dp[i] += dp[i - 1];
            }
        }
        return dp[1] + dp[2] + dp[3] + dp[4] + dp[5];
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(1).

3、 ... and 、 Method 2

Permutation and combination , Diaphragm method

class Solution {
    
    public int countVowelStrings(int n) {
    
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
    }
}

Complexity analysis

• Time complexity ：O(1).

• Spatial complexity ：O(1).