前往
大廳
主題

[leetcode]514. Freedom Trail

♙♲⚙\~O_O~/⚙♲♙ | 2021-07-23 12:00:08 | 巴幣 14 | 人氣 268

題目: 514. Freedom Trail
難度: Hard
目前下列解法的時間複雜度: O(ring長*ring長*key長)


題目說明

給你一個字串ring和key,類似轉盤式電話的方式從ring中拼出key,求最少步驟。
* "轉動1格"花費1步驟
* "確認輸入"花費1步驟,會輸入12點鐘方向的字元
* 一開始ring[0]在12點鐘方向


解法: dp
第1個字母直接填答案,然後
(正在拼第i個字母,轉盤轉到哪一格) -> 花了幾步
= "前一次的字母可以是轉到轉盤的哪裡而拼出來的 與 轉到現在這格"所需轉動的步數 + 按按鈕的1次
簡單來說:
dp[i_key][i_ring] <- min(dp[i_key-1][j_ring] + "number of steps rotating 'ring' from 'j_ring' to 'i_ring'" + 1)
要注意的是,為了算出步驟,還需儲存現在轉盤的狀態。並不需要,不要瞎掰好嗎。dp的格子就告訴你現在轉到哪了。


source code

創作回應

相關創作

更多創作