Math
Dynamic Programming
Combinatorics
Description
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:
Solutions
Solution 1
Python3 Java C++ Go
class Solution :
def countVowelStrings ( self , n : int ) -> int :
@cache
def dfs ( i , j ):
return 1 if i >= n else sum ( dfs ( i + 1 , k ) for k in range ( j , 5 ))
return dfs ( 0 , 0 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
private Integer [][] f ;
private int n ;
public int countVowelStrings ( int n ) {
this . n = n ;
f = new Integer [ n ][ 5 ] ;
return dfs ( 0 , 0 );
}
private int dfs ( int i , int j ) {
if ( i >= n ) {
return 1 ;
}
if ( f [ i ][ j ] != null ) {
return f [ i ][ j ] ;
}
int ans = 0 ;
for ( int k = j ; k < 5 ; ++ k ) {
ans += dfs ( i + 1 , k );
}
return f [ i ][ j ] = ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
int countVowelStrings ( int n ) {
int f [ n ][ 5 ];
memset ( f , 0 , sizeof f );
function < int ( int , int ) > dfs = [ & ]( int i , int j ) {
if ( i >= n ) {
return 1 ;
}
if ( f [ i ][ j ]) {
return f [ i ][ j ];
}
int ans = 0 ;
for ( int k = j ; k < 5 ; ++ k ) {
ans += dfs ( i + 1 , k );
}
return f [ i ][ j ] = ans ;
};
return dfs ( 0 , 0 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 func countVowelStrings ( n int ) int {
f := make ([][ 5 ] int , n )
var dfs func ( i , j int ) int
dfs = func ( i , j int ) int {
if i >= n {
return 1
}
if f [ i ][ j ] != 0 {
return f [ i ][ j ]
}
ans := 0
for k := j ; k < 5 ; k ++ {
ans += dfs ( i + 1 , k )
}
f [ i ][ j ] = ans
return ans
}
return dfs ( 0 , 0 )
}
Solution 2
Python3 Java C++ Go
class Solution :
def countVowelStrings ( self , n : int ) -> int :
f = [ 1 ] * 5
for _ in range ( n - 1 ):
s = 0
for j in range ( 5 ):
s += f [ j ]
f [ j ] = s
return sum ( f )
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public int countVowelStrings ( int n ) {
int [] f = { 1 , 1 , 1 , 1 , 1 };
for ( int i = 0 ; i < n - 1 ; ++ i ) {
int s = 0 ;
for ( int j = 0 ; j < 5 ; ++ j ) {
s += f [ j ] ;
f [ j ] = s ;
}
}
return Arrays . stream ( f ). sum ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
int countVowelStrings ( int n ) {
int f [ 5 ] = { 1 , 1 , 1 , 1 , 1 };
for ( int i = 0 ; i < n - 1 ; ++ i ) {
int s = 0 ;
for ( int j = 0 ; j < 5 ; ++ j ) {
s += f [ j ];
f [ j ] = s ;
}
}
return accumulate ( f , f + 5 , 0 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 func countVowelStrings ( n int ) ( ans int ) {
f := [ 5 ] int { 1 , 1 , 1 , 1 , 1 }
for i := 0 ; i < n - 1 ; i ++ {
s := 0
for j := 0 ; j < 5 ; j ++ {
s += f [ j ]
f [ j ] = s
}
}
for _ , v := range f {
ans += v
}
return
}
GitHub