LC.P1641[统计字典序元音字符串的数目]

题目描述

给你一个整数 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private int[][] f;
    private int n;

    public int countVowelStrings(int n) {
        f = new int[n][5];
        this.n = n;
        return dfs(0, 0);
    }

    // 表示当前已经选了i个元音字母，且最后一个元音字母是j的方案数
    private int dfs(int i, int j) {
        if (i >= n) return 1;
        if (f[i][j] != 0) return f[i][j];
        int ans = 0;
        for (int k = j; k < 5; ++k) {
            ans += dfs(i + 1, k);
        }
        f[i][j] = ans;
        return ans;
    }
}
  • 时间复杂度：$O(n \times C^2)$
  • 空间复杂度：$O(n \times C)$

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int countVowelStrings(int n) {
        int[] f = new int[]{1, 1, 1, 1, 1};
        for (int i = 0; i < n - 1; ++i) {
            int sum = 0;
            for (int j = 0; j < 5; ++j) {
                sum += f[j];
                f[j] = sum;
            }
        }
        return Arrays.stream(f).sum();
    }
}
  • 时间复杂度：$O(n \times C)$
  • 空间复杂度：$O(C)$

方法三：组合数学

1
2
3
public int countVowelStrings(int n) {
    return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24;
}
  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$