※ 引述《ZooseWu (動物園 公告)》之銘言：
: 1220. Count Vowels Permutation
: 給你一個n，表示字串的長度為n。
: 字串符合下面條件：
: - 每個字元只能是小寫的 a e i o u
: - a 字元後面只能接 e
: - e 字元後面只能接 a 或 i
: - i 字元後面不能接 i
: - o 字元後面只能接 i 或 u
: - u 字元後面只能接 a
: 求所有字串可能的數量。
: input: 1 output: 5
: 所有可能: a e i o u
: input: 2 output: 10
: 所有可能: ae ea ei ia ie io iu oi ou ua
: input: 3 output: 68
: Approach:
: 這題要把題目的條件反過來
: - a 字元只能接在 e i u 後面
: - e 字元只能接在 a i 後面
: - i 字元只能接在 e o 後面
: - o 字元只能接在 i 後面
: - u 字元只能接在 i o 後面
: 然後我們只記錄所有字串結尾是特定字元的數量
: 例如 n=2 的時候 a 有 ea ia ua ，所以 count.a = 3
: 然後每次進入下一輪 count.a = count.e + count.i + count.u
: TS code:
: function countVowelPermutation (n: number): number {
: const mod = 1000000007
: const count = { a: 1, e: 1, i: 1, o: 1, u: 1 }
: for (let i = 1; i < n; i++) {
: const prevCount = { ...count }
: count.a = (prevCount.e + prevCount.i + prevCount.u) % mod
: count.e = (prevCount.a + prevCount.i) % mod
: count.i = (prevCount.e + prevCount.o) % mod
: count.o = (prevCount.i) % mod
: count.u = (prevCount.i + prevCount.o) % mod
: }
: return Object.values(count).reduce((a, b) => a + b, 0) % mod
: }
: 我覺得這題蠻簡單的，不知道為什麼是hard
: 等等去偷看別人的答案看有沒有我遺漏的或是更好的思路
Python Code:
class Solution:
def countVowelPermutation(self, n: int) -> int:
mod = 1000000007
a,e,i,o,u = 1,1,1,1,1
for j in range(1,n):
a_next = e % mod
e_next = (a+i) % mod
i_next = (a+e+o+u) %mod
o_next = (i+u) %mod
u_next = a % mod
a,e,i,o,u = a_next,e_next,i_next,o_next,u_next
return (a+e+i+o+u) % mod
想了很久直接看解答
不過我還是不太懂迴圈裡面的規則
但對今天的問題有一些思路了
感謝動物園