難度: 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)
source code