Re: [閒聊] 每日LeetCode

[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

等等去偷看別人的答案看有沒有我遺漏的或是更好的思路

--
                                                                    Zoosewu
                              Yoututbe顯示PTT推文
                       可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698472430.A.4DD.html
推 oin1104: 大師 救我
→ ZooseWu: 救三小
推 Rushia: 大師
→ ZooseWu: 我不會寫C ㄏㄏ
→ oin1104: 我流淚了
推 ririoshi: 大師
→ ZooseWu: 你去google qs然後抄上去就好了啊
→ ZooseWu: 不然用heap sort
→ ZooseWu: 這個比較好理解
推 oin1104: 好 我要去那個了 謝謝