题目链接
题目描述
给你一个整数 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
求解思路&实现代码&运行结果
暴力递归
求解思路
- 分析题目我们可以知道，题目最终答案的字符只在元音字母中，这也就意味着我们从{‘a’,‘e’,‘i’,‘o’,‘u’}中收集答案即可；
- 题目中规定
所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前,那么我们直接按照字典序从小到大排列即可； - 接下来我们可以根据我们已经得出来的结论来设计我们的递归函数【DFS | 递归】，当然设计递归函数的方法也有很多，形式也非常的多样，这个是因人而异的，每个人编码习惯不一样，设计递归参数、返回值都是不一样的。那接下来我就来分享一下我的设计思路供大家学习参考。
递归参数:递归的参数我设计的是public int dfs(int index,char[] arr,int n)分别表示的含义是:从arr数组中选择，从index位置开始，每个结果的长度是n；递归返回值是int，表示的含义是返回最终的结果
实现代码
class Solution {
public int countVowelStrings(int n) {
char[] arr=new char[]{'a','e','i','o','u'};
return dfs(0,arr,n);
}
public int dfs(int index,char[] arr,int n){
if(n==0) return 1;
if(index>=arr.length) return 0;
int ans=0;
for(int i=index;i<arr.length;i++){
n-=1;
ans+=dfs(i,arr,n);
n+=1;
}
return ans;
}
}
运行结果
记忆化搜索
求解思路
- 暴力递归已经实现完成了，但是时间毕竟有些慢，为了解决这个问题，我们发现在递归的过程中会重复计算很多答案，所以我们通过一个缓存数组，如果之前算过该答案，此时我们直接返回就可以返回结果，避免重复计算。但是如果没有缓存过，此时需要我们继续算，最后将算好的结果收集到我们最终的数组中。
- 那怎么实现实现记忆化搜索呢？其实也很简单，我们直接根据递归中俩个可变化的参数定义一个二维数组，定义完成后需要先给其初始化，然后在递归实现的过程中先判断是否计算过，计算过就直接返回当前计算的结果给到上一层递归，没有计算过就继续计算，最后计算完成后，我们直接将答案进行一个缓存，便于接下来计算会使用到。具体的实现细节我们可以看如下的代码。
实现代码
class Solution {
public int countVowelStrings(int n) {
char[] arr=new char[]{'a','e','i','o','u'};
int[][] dp=new int[5][n+1];
for(int[] d:dp){
Arrays.fill(d,-1);
}
return dfs(0,arr,n,dp);
}
public int dfs(int index,char[] arr,int n,int[][] dp){
if(dp[index][n]!=-1) return dp[index][n];
if(n==0) return dp[index][n]=1;
if(index>=arr.length) return dp[index][n]=n==0?1:0;
int ans=0;
for(int i=index;i<arr.length;i++){
n-=1;
ans+=dfs(i,arr,n,dp);
n+=1;
}
return dp[index][n]=ans;
}
}
运行结果
动态规划
求解思路
- 定义 dp[i][j] 表示当前已经选了 i 个元音字母，且最后一个元音字母是 j 的方案数,初始时 dp[1][j]=1，最后累加求和即可。
- 发现 dp[i][j] 只与 dp[i−1][j] 有关，因此可以将二维数组压缩为一维数组，从而优化空间复杂度。
实现代码
class Solution {
public int countVowelStrings(int n) {
int[] dp = {1, 1, 1, 1, 1};
for (int i = 0; i < n - 1; ++i) {
int sum = 0;
for (int j = 0; j < 5; ++j) {
sum += dp[j];
dp[j] = sum;
}
}
return Arrays.stream(dp).sum();
}
}
运行结果
共勉
最后，我想送给大家一句一直激励我的座右铭，希望可以与大家共勉！