# 1220. Count Vowels Permutation
###### tags: `leetcode` `1220` `hard` `rewrite` `dp`

## :memo: Question

## :memo: 題意
* 給你一個數字 n，請你排出 n 個母音字母的排列順序，然後 a e i o u 都有自己可以接在後面的規則。
## :memo: hint
* 這個我有看 hint 差一點解出來。

## :memo: leetcode solution
* :medal: **思考一**:
* a 後面可以放 e
* e 後面可以放 a，i
* i 後面可以放 a，e，o，u
* o 後面可以放 i，u
* u 後面可以放 a


從上圖可以看出其實我們算到 n 會有多少個母音字母的總合就可以了。

    v_dic = {'a':['e'], 'e': ['a','i'], 'i':['a','e','o','u'],'o':['i','u'],'u':['a']}
    # 初始值 n = 1，
    ans_dic = {'a':1,'e':1,'i':1,'o':1,'u':1}   
    # 當 n = 2 時
    # ans_dic 每個字母都要走一遍
    
    # 計算要多少個字母的 dictionary
    trans_dic = {'a':0,'e':0,'i':0,'o':0,'u':0} 
    
    # 遍歷所有的母音
    for vowel in ans_dic:
        
        # next_vowel 代表下一個可以接的字母為甚麼
        
        for next_vowel in v_dic[vowel]:
            
            # ans_dic[vowel] 代表上一次母音字母有多少個 那下一個可以接的字母就有多少個
            trans_dic[next_vowel] = trans_dic[next_vowel] + ans_dic[vowel]
    
    ans_dic = trans_dic
    

## :memo: leetcode solution code

class Solution:
    def countVowelPermutation(self, n: int) -> int:   
                    
        v_dic = {'a':['e'], 'e': ['a','i'], 'i':['a','e','o','u'],'o':['i','u'],'u':['a']}

        ans_dic = {'a':1,'e':1,'i':1,'o':1,'u':1}   
        
        for _ in range(n-1):
        
            trans_dic = {'a':0,'e':0,'i':0,'o':0,'u':0} 
            
            for vowel in ans_dic:
            
                for next_vowel in v_dic[vowel]:
                
                    trans_dic[next_vowel] = (trans_dic[next_vowel]+ ans_dic[vowel]) % 1_000_000_007
                    
            ans_dic = trans_dic
            
        return sum(ans_dic.values()) % 1_000_000_007

## :memo: BigO
* 時間複雜度: O(n * 5 * 10)。
* 空間複雜度: O(5+5+10)。