1220. Count Vowels Permutation

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

  • Each character is a lower case vowel ('a''e''i''o''u')
  • Each vowel 'a' may only be followed by an 'e'.
  • Each vowel 'e' may only be followed by an 'a' or an 'i'.
  • Each vowel 'i' may not be followed by another 'i'.
  • Each vowel 'o' may only be followed by an 'i' or a 'u'.
  • Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3:

Input: n = 5
Output: 68

Constraints:

  • 1 <= n <= 2 * 10^4

这道题说是让求n个元音的全排列的个数,所谓的元音,就是 a,e,i,o,u 这五个字母。并制定了一系列的规则:a的后面只能跟e,e的后面只能跟a或i,i的后面不能跟另一个i,o的后面只能跟i或u,u的后面只能跟a。跟许多其他的求个数的题目一样,返回的结果要对一个超大数取余。根据博主多年的刷题经验,这种要对超大数字取余的题目,十有八九都是要用动态规划 Dynamic Programming 来做的,这道题也不例外。首先来考虑 DP 数组该如何定义,想想组成每个状态都有哪些必要的信息,全排列的长度肯定是必要的信息之一,还有就是当前全排列最后一个位置的字母也很重要,因为题目中的规则限定了很多相连字母之间的关系,很多组合是不能出现的。这里用一个二维 DP 数组,其中 dp[i][j] 表示长度为 i+1 的全排列的最后一个字母是 vowels[j] 的个数,其中 vowels 是元音字符数组,且初始化 dp[0][j] 为1,因为只有一个字母的话并不受任何的规则约束。

接下来就是要更新 dp[i][j],用个 for 循环将i从1遍历到n,由于元音只有5个,且各自的规则不同,所以不需要再用一个内层的 for 循环来遍历j,而且按照各自不同的规则来分别更新。通过分析题目中的规则可知,元音a前面只能有e,i,u,用 dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4] 来更新 dp[i][0]。元音e前面只能有a,i,用 dp[i - 1][0] + dp[i - 1][2] 来更新 dp[i][1]。元音i前面只能有e,o,用 dp[i - 1][1] + dp[i - 1][3] 来更新 dp[i][2]。元音o前面只能有i,用 dp[i - 1][2] 来更新 dp[i][3]。元音u前面只能有i,o,用 dp[i - 1][2] + dp[i - 1][3] 来更新 dp[i][4]。最后只要将所有的 dp[n-1][j] 都加起来就是所求结果,为了防止整型溢出,在所有的加的操作之后都对超大数取余,而且 dp 数组要定义成长整型的,参见代码如下:

class Solution {
public:
    int countVowelPermutation(int n) {
        int res = 0, M = 1e9 + 7;
        vector<char> vowels{'a', 'e', 'i', 'o', 'u'};
        vector<vector<long>> dp(n, vector<long>(5));
        for (int j = 0; j < 5; ++j) dp[0][j] = 1;
        for (int i = 1; i < n; ++i) {
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % M;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % M;
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % M;
            dp[i][3] = dp[i - 1][2];
            dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % M;
        }
        for (int j = 0; j < 5; ++j) {
            res = (res + dp[n - 1][j]) % M;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1220

参考资料:

https://leetcode.com/problems/count-vowels-permutation/

https://leetcode.com/problems/count-vowels-permutation/discuss/398222/Detailed-Explanation-using-Graphs-With-Pictures-O(n)

https://leetcode.com/problems/count-vowels-permutation/discuss/398173/C%2B%2B-Bottom-up-Recursive-DPs-O(n)-and-Matrix-Exponentiation-O(logn)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation