使用特殊打字机键入单词的最少时间

难度: Easy

有一个特殊打字机，它由一个圆盘和一个指针组成，圆盘上标有小写英文字母 'a' 到 'z'。只有当指针指向某个字母时，它才能被键入。指针 初始时 指向字符 'a' 。

每一秒钟，你可以执行以下操作之一：

将指针 顺时针 或者 逆时针 移动一个字符。
键入指针当前指向的字符。

给你一个字符串 word ，请你返回键入 word 所表示单词的最少秒数。

示例 1：

输入：word = "abc"
输出：5
解释：
单词按如下操作键入：
- 花 1 秒键入字符 'a' in 1 ，因为指针初始指向 'a' ，故不需移动指针。
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 1 秒将指针顺时针移到 'c' 。
- 花 1 秒键入字符 'c' 。

示例 2：

输入：word = "bza"
输出：7
解释：
单词按如下操作键入：
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 2 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 1 秒将指针顺时针移到 'a' 。
- 花 1 秒键入字符 'a' 。

示例 3：

输入：word = "zjpc"
输出：34
解释：
单词按如下操作键入：
- 花 1 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 10 秒将指针顺时针移到 'j' 。
- 花 1 秒键入字符 'j' 。
- 花 6 秒将指针顺时针移到 'p' 。
- 花 1 秒键入字符 'p' 。
- 花 13 秒将指针逆时针移到 'c' 。
- 花 1 秒键入字符 'c' 。

提示：

1 <= word.length <= 100
word 只包含小写英文字母。

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def minTimeToType(self, word: str) -> int:
        res = 0
        ans = 0
        for w in word:
            num = ord(w) - ord('a')
            ans += min((num - res) % 26,(res - num) % 26) + 1
            res = num
        return ans

Explain

此题解的核心思想是模拟打字机键入单词的过程，同时计算完成整个操作所需的最少秒数。打字机的指针初始位置在'a'，所以对于字符串中的每个字符，我们需要计算指针从当前位置到该字符的最短距离（无论是顺时针还是逆时针）。每一次操作包括移动指针到目标字母，然后键入该字符。移动指针到目标字母的最小秒数可以通过计算顺时针和逆时针两种方式的距离，然后取较小值来实现。最后将所有操作的秒数累加起来即得到结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minTimeToType(self, word: str) -> int:
        # res记录当前指针位置对应的字符（转换为从'a'开始的索引值）
        res = 0
        # ans记录总的操作秒数
        ans = 0
        # 遍历输入的字符串
        for w in word:
            # 将字符转换为从'a'开始的索引值
            num = ord(w) - ord('a')
            # 计算移动到当前字符的最短距离并加上键入该字符的1秒
            ans += min((num - res) % 26, (res - num) % 26) + 1
            # 更新当前指针位置
            res = num
        # 返回总的操作秒数
        return ans

Explore

在题解中，顺时针和逆时针的距离计算是基于英文字母表的循环特性。假设当前指针位置为 `res`，目标字母的位置为 `num`。顺时针距离是指从当前位置 `res` 直接向前移动到 `num` 的距离，可以通过 `(num - res) % 26` 来计算。如果 `num` 大于 `res`，这个值就是两者的直接差；如果 `num` 小于 `res`，则 `% 26` 确保我们计算的是通过字母表末尾回到开头的循环距离。逆时针距离是指从 `res` 向后移动到 `num` 的距离，可以通过 `(res - num) % 26` 来计算。这同样利用了 `% 26` 来处理循环回滚的情况。

在英文字母表中，一共有26个字母，从`a`到`z`。使用 `% 26` 的模运算是为了处理字母表的循环特性。当指针移动超过 `z` 时，它会自动回到 `a`，形成一个闭环。同样，如果向逆时针方向越过 `a`，也会回到 `z`。因此，`% 26` 确保无论指针如何移动，都能正确地计算出从一个字母到另一个字母的最短距离，考虑到字母表的循环结构。

在每次操作中加1秒代表的是打字机键入一个字符所需的时间。这意味着，除了计算指针从一个字母移动到另一个字母所需的时间外，每当指针到达一个字母后，还需要额外1秒来实际键入该字母。因此，每次移动指针到目标字母的时间外，还必须加上键入该字母本身所需的1秒。这样的计算确保了题解中的总时间既包括了移动指针的时间，也包括了键入每个字符的时间。