[LeetCode] 1220. Count Vowels Permutation

 Problem : https://leetcode.com/problems/count-vowels-permutation/

In one state, we remember the number of permutations end by a particular vowel letter. Then the next state can be built upon the current state base on the given extending rule.

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels = {v: 1 for v in ['a', 'e', 'i', 'o', 'u']}
        
        for i in range(1, n):
            tmp = {}
            # extend permutations by appending 'a'
            tmp['a'] = vowels['e'] + vowels['u'] + vowels['i']
            # extend permutations by appending 'e'
            tmp['e'] = vowels['a'] + vowels['i']
            # extend permutations by appending 'i'
            tmp['i'] = vowels['e'] + vowels['o']
            # extend permutations by appending 'o'
            tmp['o'] = vowels['i']
            # extend permutations by appending 'u'
            tmp['u'] = vowels['o'] + vowels['i']
            # move to the next state
            vowels = tmp
        
        return sum(vowels.values()) % (10**9 + 7)