leetcode 1220

问题

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:

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

Example 2:

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

Example 3: 

1
2
Input: n = 5
Output: 68

Constraints:

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

分析

两种分析思路，第一种是考虑每个字符后面能接哪些字符，另一种是考虑一个字符能接在以哪些字符串结尾的后面。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int countVowelPermutation(int n) {
        vector<vector<int>> dp(n, vector<int>(5, -1));
        vector<vector<int>> e = {
            {1},
            {0, 2},
            {0, 1, 3, 4},
            {2, 4},
            {0}
        };
        
        long long ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans += dfs(dp, e, n-1, i);
        }
        return ans%1000000007;
    }

    int dfs(vector<vector<int>> &dp, vector<vector<int>> &e, int remaind, int last) {
        if (remaind == 0)
            return 1;
        if (dp[remaind][last] >= 0)
            return dp[remaind][last];
        
        long long ret = 0;
        for (int y: e[last]) {
            ret += dfs(dp, e, remaind-1, y);
        }
        return dp[remaind][last] = ret%1000000007;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countVowelPermutation(int n) {
        vector<long long> dp(5), dp2;
        for (int i = 0; i < 5; ++i) {
            dp[i] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            dp2 = dp;
            dp[0] = (dp2[1] + dp2[2] + dp2[4])%1000000007;
            dp[1] = (dp2[0] + dp2[2])%1000000007;
            dp[2] = (dp2[1] + dp2[3])%1000000007;
            dp[3] = dp2[2];
            dp[4] = (dp2[2] + dp2[3])%1000000007;
        }
        
        long long ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans += dp[i];
        }
        return ans%1000000007;
    }
};