Hard

题目描述

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

  • 字符串中的每个字符都应当是小写元音字母（‘a’, ’e’, ‘i’, ‘o’, ‘u’）
  • 每个元音 ‘a’ 后面都只能跟着 ’e’
  • 每个元音 ’e’ 后面只能跟着 ‘a’ 或者是 ‘i’
  • 每个元音 ‘i’ 后面不能再跟着另一个 ‘i’
  • 每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’
  • 每个元音 ‘u’ 后面只能跟着 ‘a’

由于答案可能会很大，所以请你返回 模 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

提示：

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

解题思路

这是一道典型的动态规划题目，核心思想是根据题目给出的转移规则来构建状态转移方程。

首先分析转移规则：

  • ‘a’ 只能跟着 ’e’
  • ’e’ 能跟着 ‘a’ 或 ‘i’
  • ‘i’ 能跟着 ‘a’, ’e’, ‘o’, ‘u’（除了’i’）
  • ‘o’ 能跟着 ‘i’ 或 ‘u’
  • ‘u’ 只能跟着 ‘a’

我们可以用 dp[i][j] 表示长度为 i 且以第 j 个元音结尾的字符串数量，其中 j=0,1,2,3,4 分别对应 ‘a’,’e’,‘i’,‘o’,‘u’。

状态转移方程为：

  • dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4] （以’a’结尾，可由’e’,‘i’,‘u’转移而来）
  • dp[i][1] = dp[i-1][0] + dp[i-1][2] （以’e’结尾，可由’a’,‘i’转移而来）
  • dp[i][2] = dp[i-1][1] + dp[i-1][3] （以’i’结尾，可由’e’,‘o’转移而来）
  • dp[i][3] = dp[i-1][2] （以’o’结尾，只能由’i’转移而来）
  • dp[i][4] = dp[i-1][2] + dp[i-1][3] （以’u’结尾，可由’i’,‘o’转移而来）

初始状态：dp[1][j] = 1 对所有 j。

为了优化空间复杂度，我们可以使用滚动数组，只保存当前和前一个状态。

代码实现

class Solution {
public:
    int countVowelPermutation(int n) {
        const int MOD = 1000000007;
        
        long long a = 1, e = 1, i = 1, o = 1, u = 1;
        
        for (int len = 2; len <= n; len++) {
            long long newA = (e + i + u) % MOD;
            long long newE = (a + i) % MOD;
            long long newI = (e + o) % MOD;
            long long newO = i % MOD;
            long long newU = (i + o) % MOD;
            
            a = newA;
            e = newE;
            i = newI;
            o = newO;
            u = newU;
        }
        
        return (a + e + i + o + u) % MOD;
    }
};

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 1000000007
        
        a, e, i, o, u = 1, 1, 1, 1, 1
        
        for length in range(2, n + 1):
            new_a = (e + i + u) % MOD
            new_e = (a + i) % MOD
            new_i = (e + o) % MOD
            new_o = i % MOD
            new_u = (i + o) % MOD
            
            a, e, i, o, u = new_a, new_e, new_i, new_o, new_u
        
        return (a + e + i + o + u) % MOD

public class Solution {
    public int CountVowelPermutation(int n) {
        const int MOD = 1000000007;
        
        long a = 1, e = 1, i = 1, o = 1, u = 1;
        
        for (int len = 2; len <= n; len++) {
            long newA = (e + i + u) % MOD;
            long newE = (a + i) % MOD;
            long newI = (e + o) % MOD;
            long newO = i % MOD;
            long newU = (i + o) % MOD;
            
            a = newA;
            e = newE;
            i = newI;
            o = newO;
            u = newU;
        }
        
        return (int)((a + e + i + o + u) % MOD);
    }
}

var countVowelPermutation = function(n) {
    const MOD = 1000000007;
    
    let a = 1, e = 1, i = 1, o = 1, u = 1;
    
    for (let len = 2; len <= n; len++) {
        let newA = (e + i + u) % MOD;
        let newE = (a + i) % MOD;
        let newI = (e + o) % MOD;
        let newO = i % MOD;
        let newU = (i + o) % MOD;
        
        a = newA;
        e = newE;
        i = newI;
        o = newO;
        u = newU;
    }
    
    return (a + e + i + o + u) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历从2到n的所有长度
空间复杂度O(1)只使用了常数个变量存储状态

相关题目