频道首页
目录
统计字典序元音字符串的数目
收藏
0
给你一个整数 n
,请返回长度为 n
、仅由元音 (a
, e
, i
, o
, u
) 组成且按 字典序排列 的字符串数量。
字符串 s
按 字典序排列 需要满足:对于所有有效的 i
,s[i]
在字母表中的位置总是与 s[i+1]
相同或在 s[i+1]
之前。
原题链接:
1641. 统计字典序元音字符串的数目 - 力扣(Leetcode)
实例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
首先我们很容易分析出来这个题就是让我们在这五个字母中求长度为 n 的顺序,我们使用 0 ,1 ,2, 3, 4,这几个数字来代替这五个字符,定义dp[ i] [ j ]表示以i结尾的长度为 j的字符串长度个数我们可以很容易的到转移方程
这里我写了前几组如下:
dp【i】[ j ]是由左边和上边相加推导出的
class Solution {
public int countVowelStrings(int n) {
int[][] dp = new int[n + 3][6];
Arrays.fill(dp[1], 1);
if(n == 1)return 5;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= 5; j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
int ans = 0;
for(int i = 1; i <=5; i++){
ans += dp[n][i];
}
return ans;
}
}
这道题和最长公共子序列的dp问题有点相似:
主页
会议室
Git管理
文章
云文档
看板