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

题目链接

Leetcode.1641 统计字典序元音字符串的数目 Rating ： 1519

题目描述

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

提示：

• $1<=n<=50$

解法：线性dp

我们定义 $f(i,j)$ 为一共 i个字符，以字符 j（1 -> a , 2 -> e , 3 -> i , 4 -> o , 5 -> u）结尾的方案数。

按照定义，最终的答案就为 $f(n,1)+f(n,2)+f(n,3)+f(n,4)+f(n,5)$

因为必须按字典序排序：

• a只能接在 a后面，即 $f(i,1)=f(i-1,1)$
• e只能接在 a和 e后面，即 $f(i,2)=f(i-1,2)+f(i-1,1)$
• i只能接在 a , e , i后面，即 $f(i,3)=f(i-1,3)+f(i-1,2)+f(i-1,1)$
• 剩下的两个同理。。。

时间复杂度：$O(5!\ast n)$

C++代码：

class Solution {
public:
    int countVowelStrings(int n) {
        int f[n + 1][6];

        memset(f,0,sizeof f);

        f[0][0] = 1;

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= 5;j++){
                for(int k = 0;k <= j;k++) f[i][j] += f[i-1][k];
            }
        }

        int ans = 0;
        for(int i = 1;i <= 5;i++) ans += f[n][i];

        return ans;
    }
};