统计字典序元音字符串的数目

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

示例 1：

输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：
输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：
输入：n = 33
输出：66045
 
提示：

1 <= n <= 50 
通过次数5,190提交次数6,595

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-sorted-vowel-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一看到排列组合就想到了回溯

class Solution {

    public int count = 0;
    public int countVowelStrings(int n) {
        backtrack(0, 0, n);
        return count;
    }

    public void backtrack(int start, int deep, int maxDeep) {
        if (deep >= maxDeep) {
            count++;
            return;
        }
        for (int i = start; i < 5; i++) {
            backtrack(i, deep + 1, maxDeep);
        }
    }
}

动态规划方法

一维动归

class Solution {
    public int countVowelStrings(int n) {
        int[] dp = new int[]{1, 1, 1, 1, 1};
        for(int i = 1;i < n;i++) {
            for(int j = 1;j < 5;j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
    }
}

二维动归

class Solution {
    public int countVowelStrings(int n) {
        int[][] dp = new int[n][5];
        dp[0][0] = 1;
        dp[0][1] = 2;
        dp[0][2] = 3;
        dp[0][3] = 4;
        dp[0][4] = 5;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 5; ++j) {
                if (j == 0){
                    dp[i][j] = dp[i-1][j];
                } 
                else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                } 
            }
        }
        return dp[n-1][4];
    }
}

参考文献

fzt01057的评论

听韬声画倩影的评论

赏

谢谢你请我吃糖果

微信