1220. Count Vowels Permutation

Difficulty:
Related Topics:
Similar Questions:

    Problem

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

    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:

    Solution

    /**
     * @param {number} n
     * @return {number}
     */
    var countVowelPermutation = function(n) {
        var dp = Array(n).fill(0).map(() => ({}));
        return helper('', n, dp);
    };
    
    var helper = function(lastChar, n, dp) {
        if (n === 0) return 1;
        if (dp[n - 1][lastChar] !== undefined) return dp[n - 1][lastChar];
        var mod = Math.pow(10, 9) + 7;
        var res = 0;
        if (!lastChar || lastChar === 'e') res = (res + helper('a', n - 1, dp)) % mod;
        if (!lastChar || lastChar === 'a' || lastChar === 'i') res = (res + helper('e', n - 1, dp)) % mod;
        if (!lastChar || lastChar !== 'i') res = (res + helper('i', n - 1, dp)) % mod;
        if (!lastChar || lastChar === 'i' || lastChar === 'u') res = (res + helper('o', n - 1, dp)) % mod;
        if (!lastChar || lastChar === 'a') res = (res + helper('u', n - 1, dp)) % mod;
        dp[n - 1][lastChar] = res;
        return res;
    };
    

    Explain:

    nope.

    Complexity: