---
# System prepended metadata

title: 1220. Count Vowels Permutation
tags: [dp, leetcode, hard, rewrite, '1220']

---

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

## :memo:  Question
![](https://i.imgur.com/wjKXY5W.png)


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

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

![](https://i.imgur.com/IAr2Oyc.png)

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


 ```python=
    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
```python=
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)。