Hexo

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

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

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