Medium

题目描述

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

解题思路

这是一个经典的动态规划问题，核心思想是统计满足非降序排列的元音字符串数量。

思路分析：

由于字符串必须按字典序排列，这意味着后面的字符不能小于前面的字符。我们可以用动态规划来解决：

  1. 状态定义：dp[i][j] 表示长度为 i，以第 j 个元音字母结尾的字符串数量
  2. 状态转移：对于位置 i，如果当前字符是第 j 个元音，那么前一个字符可以是第 0 到第 j 个元音中的任意一个
  3. 优化思路：我们可以进一步优化空间，只用一维数组，因为每次只依赖前一层的结果

数学解法： 这个问题实际上等价于求"从5个元音字母中允许重复地选择n个字母，且选择顺序非降序"的方案数，这是一个经典的组合数学问题，答案是 C(n+4, 4)。

三种解法：

  1. 二维DP：时间O(n)，空间O(n)
  2. 一维DP（推荐）：时间O(n)，空间O(1)
  3. 数学公式：时间O(1)，空间O(1)

这里给出最直观易懂的一维DP解法。

代码实现

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

class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [1] * 5
        
        for i in range(2, n + 1):
            for j in range(3, -1, -1):
                dp[j] += dp[j + 1]
        
        return sum(dp)

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

var countVowelStrings = function(n) {
    let dp = [1, 1, 1, 1, 1];
    
    for (let i = 2; i <= n; i++) {
        for (let j = 3; j >= 0; j--) {
            dp[j] += dp[j + 1];
        }
    }
    
    return dp.reduce((sum, val) => sum + val, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n) - 需要进行n-1轮迭代，每轮进行常数次操作
空间复杂度O(1) - 只使用了固定大小的数组来存储5个元音的状态