Leetcode 1220:统计元音字母序列的数目(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1220:统计元音字母序列的数目(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数 n,请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串:

由于答案可能会很大,所以请你返回 模 10^9 + 7 之后的结果。

示例 1:

输入:n = 1
输出:5
解释:所有可能的字符串分别是:"a", "e", "i" , "o" 和 "u"。

示例 2:

输入:n = 2
输出:10
解释:所有可能的字符串分别是:"ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。

示例 3:

输入:n = 5
输出:68

提示:

解题思路

首先这个问题不难想到dfs,也就是每次判断前面的字符是什么,然后当前有几种选法,我这里就不写了,这么做会递归过深。所以采用动态规划,先思考一下前后的变换关系。

那么a=e+i+ue=a+ii=e+oo=iu=i+o,这就是转移方程。

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a, e, i, o, u = 1, 1, 1, 1, 1
        for _ in range(n - 1):
            a, e, i, o, u = e + i + u, a + i, e + o, i, i + o
        return (a + e + i + o + u) % (10**9 + 7)

实际上这个问题和Leetcode 935:骑士拨号器(超详细的解法!!!)非常类似,而且还比它简单。

reference:

https://leetcode.com/problems/count-vowels-permutation/discuss/398286/Simple-Python-(With-Diagram)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses