Day 23：1974. Minimum Time to Type Word Using Special Typewriter

今日题目

题目连结：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