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

---

解法1

从1到n的计算就好了. 注意就是已经计算过的数字用一个二维数组memo保存起来

class Solution {
    
    public static Map<Character, Integer> map = new HashMap<>();
    static {
        map.put('a' , 0);
        map.put('e' , 1);
        map.put('i' , 2);
        map.put('o' , 3);
        map.put('u' , 4);
    }
    int mod = 1000000007;
    
    public int countVowelPermutation(int n) {
        int[][] memo = new int[5][n + 2];
        return (helper('i', n + 1, memo) + helper('i', n, memo)) % mod;
    }
    
    private int helper(char c, int n, int[][] memo){
        if(n == 1)
            return 1;
        
        int index = map.get(c);
        if(memo[index][n] > 0)
            return memo[index][n];
        
        int res = 0;
        
        switch(c){
            case 'a':
                res = helper('e', n - 1, memo);
                break;
            case 'e':
                res = helper('a', n - 1, memo) + helper('i', n - 1, memo);
                break;
            case 'i':
                res = (helper('a', n - 1, memo) + helper('e', n - 1, memo))% mod + (helper('o', n - 1, memo) + helper('u', n - 1, memo))% mod;
                break;
            case 'o':
                res = helper('i', n - 1, memo) + helper('u', n - 1, memo);
                break;
            case 'u':
                res = helper('a', n - 1, memo);
                break;
        }
        
        memo[index][n] = res % mod;
        return memo[index][n];
    }
}

---

解法2

更简洁明了的写法. 其实并不需要保存所有的中间值.只需要保存前一次计算的值就好了.

class Solution {
    public int countVowelPermutation(int n) {
        long aCount = 1, eCount = 1, iCount = 1, oCount = 1, uCount = 1;
        int MOD = 1000000007;

        for (int i = 1; i < n; i++) {
            long aCountNew = (eCount + iCount + uCount) % MOD;
            long eCountNew = (aCount + iCount) % MOD;
            long iCountNew = (eCount + oCount) % MOD;
            long oCountNew = (iCount) % MOD;
            long uCountNew = (iCount + oCount) % MOD;
            aCount = aCountNew;
            eCount = eCountNew;
            iCount = iCountNew;
            oCount = oCountNew;
            uCount = uCountNew;
        }
        long result = (aCount + eCount + iCount + oCount + uCount)  % MOD;
        return (int)result;
    }
}