首页 > 其他 > 详细

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

时间:2021-01-04 22:59:19      阅读:25      评论:0      收藏:0      [点我收藏+]
题干

给你一个整数 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 

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/count-sorted-vowel-strings

 

思路

用动态规划,找递推公式

①定义nums[i][j]二位数组

i代表a=1,e=2,i=3,o=4,u=5;以i为结束的字符串

j代表长度为j的字符串

num[i][j]代表,以i为结尾的长度为j的字符串的数量

②找递推公式

写出开头几个递推式子,通过递归式子找规律

nums[i][j]=nums[i-1][j]+nums[i][j-1];

③初始化边界值

定义n=1和2时返回值

初始化以0为基数的值

class Solution {
    public int countVowelStrings(int n) {
        if(n==1){
            return 5;
        }
        else if(n==2){
            return 15;
        }
        //定义以以aeiou为结尾的,长度为i的排序个数
        int[][] nums=new int[6][n+1];
        //初始化边边角角
        for(int i=0;i<=n;i++){
            nums[0][i]=0;
        }
        nums[1][0]=0;
        nums[2][0]=0;
        nums[3][0]=0;
        nums[4][0]=0;
        nums[5][0]=0;
        //初始化以i结尾长度为1的方法
        nums[1][1]=1;
        nums[2][1]=1;
        nums[3][1]=1;
        nums[4][1]=1;
        nums[5][1]=1;
        //初始化以i结尾长度为2的方法
        nums[1][2]=nums[1][1];
        nums[2][2]=nums[1][1]+nums[2][1];
        nums[3][2]=nums[1][1]+nums[2][1]+nums[3][1];
        nums[4][2]=nums[1][1]+nums[2][1]+nums[3][1]+nums[4][1];
        nums[5][2]=nums[1][1]+nums[2][1]+nums[3][1]+nums[4][1]+nums[5][1];
        //初始化以i结尾长度为3的方法
        nums[1][3]=nums[0][3]+nums[1][2];
        nums[2][3]=nums[1][3]+nums[2][2];
        nums[3][3]=nums[2][3]+nums[3][2];
        nums[4][3]=nums[3][3]+nums[4][2];
        nums[5][3]=nums[4][3]+nums[5][2];
        //nums[i][j]=nums[i-1][j]+nums[i][j-1];
        for(int i=1;i<=5;i++){
            for(int j=2;j<=n;j++){
                nums[i][j]=nums[i-1][j]+nums[i][j-1];
            }
        }
        return nums[1][n]+nums[2][n]+nums[3][n]+nums[4][n]+nums[5][n];
    }
}

 

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

原文:https://www.cnblogs.com/ak918xp/p/14232691.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!