source: https://leetcode.com/problems/count-sorted-vowel-strings/description/
Count Sorted Vowel Strings
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"].
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.
Example 3:
Input: n = 33
Output: 66045
Constraints:
1 <= n <= 50
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public int countVowelStrings(int n) { int[][] memo = new int[n+1][6]; for(int[] m: memo){ Arrays.fill(m, -1); } return dfs(n, 0, memo); } private int dfs(int n, int index, int[][] memo){ //if n == 0 we have completed a String of length n //return 1 if(n==0){ return 1; } if(memo[n][index] !=-1) return memo[n][index]; int count = 0; for(int i=index;i<5;i++){ count = count + dfs(n-1, i, memo); } memo[n][index] = count; return count; } } |