1220.md

1220. Count Vowels Permutation

Solution 1 (time O(n), space O(n))

# Dynamic Programming
class Solution(object):
    def countVowelPermutation(self, n):
        """
        :type n: int
        :rtype: int
        """
        mod = 10 ** 9 + 7
        dp_a = [0 for _ in range(n)]
        dp_e = [0 for _ in range(n)]
        dp_i = [0 for _ in range(n)]
        dp_o = [0 for _ in range(n)]
        dp_u = [0 for _ in range(n)]
        dp_a[0] = dp_e[0] = dp_i[0] = dp_o[0] = dp_u[0] = 1
        for i in range(1, n):
            dp_a[i] = (dp_e[i - 1] + dp_i[i - 1] + dp_u[i - 1]) % mod
            dp_e[i] = (dp_a[i - 1] + dp_i[i - 1]) % mod
            dp_i[i] = (dp_e[i - 1] + dp_o[i - 1]) % mod
            dp_o[i] = dp_i[i - 1] % mod
            dp_u[i] = (dp_i[i - 1] + dp_o[i - 1]) % mod
        return (dp_a[-1] + dp_e[-1] + dp_i[-1] + dp_o[-1] + dp_u[-1]) % mod