1641. Count Sorted Vowel Strings

1641. Count Sorted Vowel Strings

Question

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.

Solution

动态规划,创建数组dp[]记录以每个字符开头能组成的字符串数量。
由于当长度为1时,每个字符串都能组成一次,因此初始化所有值为1。

n增长时,每一个层级都等于该字符后的所有值相加。
最后得出的结果在下一个层级的第一位。(因为第一位是所有上一个层级加和)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int countVowelStrings(int n) {
int[] dp = new int[]{1,1,1,1,1};

for(int i = 0; i < n; i++){
for(int j = 0; j < 5; j++){
for(int k = j+1; k < 5; k++){
dp[j] += dp[k];
}
}
}
return dp[0];
}
}

Solution

递归,使用成员变量计算有效递归次数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
int count;
public int countVowelStrings(int n) {
count = 0;
count(n, 0);
return count;
}

private void count(int n, int start){
if(n == 0){
count++;
return;
}
for(int i = start; i < 5; i++){
count(n-1, i);
}
}
}
Author

Xander

Posted on

2022-05-11

Updated on

2022-05-12

Licensed under

Comments