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
等等去偷看別人的答案看有沒有我遺漏的或是更好的思路