今日題目

題目連結：1974. Minimum Time to Type Word Using Special Typewriter
題目主題：String, Greedy

簡單說說 Greedy

Greedy 貪婪法，很常聽見的演算法之一，Greedy 在解問題時，會把問題拆成每個小步前進，過程中的每一步都只會選擇當下的最佳答案，但這每一小步前進最終得到的答案不見得會是問題的最佳解。有些問題是可以得到最佳解的，但不一定每種問題都可以得到最佳解。

假設現在要從 A 走到 D ，用 Greedy 方法來解的話，過程如下圖：

可以看到這樣的過程，每走一步都是選擇當下的最佳路徑，路徑解答會是 2 + 1 + 2 = 5，在這個狀況下是最佳解答，但如果把題目稍微改一下，將上面的 2 改成 4，可能就得不到最佳解答了，如下：

這樣子用 Greedy 還是會走紅色的路線，這樣得到的答案就是 2 + 1 + 4 = 7，但實際上以這個狀態最佳解就會是綠色路徑 2 + 4 = 6，這就是 Greedy 可能拿不到最佳解的例子。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

這是一個 a ~ z 的一個特殊的圓型打字機，下圖是LeetCode上面的範例圖：

上面會有一個指針，當指針指到某個英文字母時才能輸入目前指到的英文字母，這個指針最初預設會停在 'a'。

規則是，每一秒只能做一個動作，能操作的動作如下：

• 將指針順時針或逆時針移動一個字
• 輸入目前指到的英文字母

題目會給一個 word 字串，目標是用最短秒數打完這組字串，最終回傳這個最短秒數。

約束：

• 1 <= word.length <= 100
• word 只會由小寫英文字母組成

範例1

輸入: word = "abc"
輸出: 5
解說: 
打字機的移動過程如下:
- 因為預設停在 'a' ， 直接輸入 'a' 花了 1 秒。
- 將指針移動到 'b' 往順時鐘移動一步花了 1 秒。
- 輸入 'b' 花了 1 秒。
- 將指針移動到 'c' 往順時鐘移動一步花了 1 秒。
- 輸入 'c' 花了 1 秒。

範例2

輸入: word = "bza"
輸出: 7
解說:
打字機的移動過程如下:
- 將指針移動到 'b' 往順時鐘移動一步花了 1 秒。
- 輸入 'b' 花了 1 秒。
- 將指針移動到 'z' 往逆時鐘移動兩步花了 2 秒。
- 輸入 'z' 花了 1 秒。
- 將指針移動到 'a' 往順時鐘移動一步花了 1 秒。
- 輸入 'a' 花了 1 秒。

範例3

輸入: word = "zjpc"
輸出: 34
解說:
打字機的移動過程如下:
- 將指針移動到 'z' 往逆時鐘移動一步花了 1 秒。
- 輸入 'z' 花了 1 秒。
- 將指針移動到 'j' 往順時鐘移動花了 10 秒。
- 輸入 'j' 花了 1 秒。
- 將指針移動到 'p' 往順時鐘移動花了 6 秒。
- 輸入 'p' 花了 1 秒。
- 將指針移動到 'c' 往順時鐘移動花了 13 秒。
- 輸入 'c' 花了 1 秒。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告兩個變數：
   • seconds: 紀錄總秒數。
   • nowWord: 紀錄目前指針指到的英文字母。
2. 跑一個迴圈，走過 word 中每個英文字母：
   • 算出 nowWord 移動到目前字母的移動秒數。
     • 將兩個字母轉成 ASCII 數字，相減的絕對值就是移動秒數
   • 若移動秒數超過 26/2 字母的一半，代表往另一個方向移動會比較快，反方向移動秒數的計算方式用 26個字母 - 移動秒數就可以得到。 Ex. a 移到 o = 14，反方向就會是 26 - 14 = 12，秒數會比較短。
   • 移動到目前的字母後，將移動秒數 + 輸入的 1 秒再加進 seconds，並將 nowWord 指定到目前的字母上。
3. 最終回傳 seconds 總秒數。

圖解過程

範例：word = "fuc"

下圖是第一個步驟，中間的指針預設在 'a' 字母上面，移動綠色路線到 'f' 花了 5 秒鐘，加 1 是因為還要輸入花 1 秒鐘，而中間的seconds會將目前花的秒數加總起來。

接著上個步驟指針停在 'f' 上面，移到 'u'，走紅色路線 15 秒，超過 26 / 2 的 13，因此往反方向走綠色路線，26 - 15 = 11，加上輸入要花的 1 秒鐘，之後 seconds 再加上目前的秒數。

繼續從 'u' 移到 'c'，走紅色路線 18 秒，超過 26 / 2 的 13，往反方向走綠色路線，26 - 18 = 8，加上輸入要花的 1 秒鐘，之後 seconds 再加上目前的秒數得到總秒數 27。

最終這個範例會回傳總秒數 27 秒。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def minTimeToType(self, word: str) -> int:
        # 紀錄花費秒數
        seconds = 0
        # 紀錄目前指針指導的英文字母
        nowWord = 'a'
        # 將 word 中每個字走一次
        for idx in range(len(word)):
            # 算出需移動的秒數
            moveSeconds = abs(ord(word[idx]) - ord(nowWord))
            # 若超過一半代表往反方向走比較快
            # 26個英文字母 - 移動秒數 = 反方向的移動秒數
            if moveSeconds > (26/2):
                moveSeconds = 26 - moveSeconds
            # 每次找到一個字除了移動秒數以外，+1 是輸入秒數
            seconds += (moveSeconds + 1)
            # 將指針指定到目前的英文字母上
            nowWord = word[idx]
        return seconds

希望您今天能瞭解到...

1. Greedy 的基本概念
2. 1974.Minimum Time to Type Word Using Special Typewriter 的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：605. Can Place Flowers