題目敘述
題目會給定一組規則，要求我們計算給定長度下的母音直線排列有幾種?
規則:a 後面只能接e
e 後面只能接a 或 i
i 後面不能接 i (換句話說，接i之外的母音都可以)
o 後面只能接i 或 u
u 後面只能接a
最後回傳答案前，要求對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:
1 <= n <= 2 * 10^4
演算法
依照轉換規則，推導出對應的狀態轉移遞迴關係式:
a 後面只能接e
e 後面只能接a 或 i
i 後面不能接 i (換句話說，接i之外的母音都可以)
o 後面只能接i 或 u
u 後面只能接a
=> 推導出
a 後面只能接e
e 後面只能接a 或 i
i 後面只能接a, 或 e, 或 o, 或 u
o 後面只能接i 或 u
u 後面只能接a
=> 推導出
a結尾的字串來自 前一個e結尾的字串, 前一個i結尾的字串, 前一個u結尾的字串
e結尾的字串來自 前一個a結尾的字串, 前一個i結尾的字串
i結尾的字串來自 前一個e結尾的字串, 前一個o結尾的字串
o結尾的字串來自 前一個i結尾的字串
u結尾的字串來自 前一個i結尾的字串, 前一個o結尾的字串
初始條件: 一開始長度為一的方法數各有一種，分別是
a, e, i, o, u 本身，對應到字串長度1,1,1,1,1
造一個迴圈，從長度為2開始往上更新每個母音結尾的直線排列數。
最後，回傳答案前，記得對10^9 + 7做除法取餘數。
程式碼
class Solution:
def countVowelPermutation(self, n: int) -> int:
modulo = 10**9 + 7
# initialization for length of permutation = 1
(a, e, i, o, u) = (1, 1, 1, 1, 1)
length_of_permutation = 2
while length_of_permutation <= n:
# update total method count by transition rule
end_with_a = e + i + u
end_with_e = a + i
end_with_i = e + o
end_with_o = i
end_with_u = i + o
# update method count of ending with a e i o u
(a, e, i, o, u) = (end_with_a, end_with_e, end_with_i, end_with_o, end_with_u )
length_of_permutation += 1
return (a + e + i + o + u) % modulo
複雜度分析
時間複雜度:
O( n ) bottom-up 從 字串長度為1 開始遞迴更新到 字串長度為n。
空間複雜度:
O( 1 ) 使用到的都是臨時變數，所佔用記憶體空間為常數級別。
關鍵知識點
關鍵在於從題目給的字串規則，推導出每個母音結尾的遞迴狀態轉移關係式。
Reference:
[1] Python O(1) aux space by DP. 70%+ [w/ Comment] - Count Vowels Permutation - LeetCode
