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; } } |