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

题目描述

有一个特殊打字机，它由一个圆盘和一个指针组成，圆盘上标有小写英文字母 '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 只包含小写英文字母。

解法

方法一：贪心

我们初始化答案变量 \(\textit{ans}\) 为字符串的长度，表示我们至少需要 \(\textit{ans}\) 秒来键入字符串。

接下来，我们遍历字符串，对于每个字符，我们计算当前字符和前一个字符之间的最小距离，将这个距离加到答案中。然后我们更新当前字符为前一个字符，继续遍历。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def minTimeToType(self, word: str) -> int:
        ans, a = len(word), ord("a")
        for c in map(ord, word):
            d = abs(c - a)
            ans += min(d, 26 - d)
            a = c
        return ans

class Solution {
    public int minTimeToType(String word) {
        int ans = word.length();
        char a = 'a';
        for (char c : word.toCharArray()) {
            int d = Math.abs(a - c);
            ans += Math.min(d, 26 - d);
            a = c;
        }
        return ans;
    }
}

class Solution {
public:
    int minTimeToType(string word) {
        int ans = word.length();
        char a = 'a';
        for (char c : word) {
            int d = abs(a - c);
            ans += min(d, 26 - d);
            a = c;
        }
        return ans;
    }
};

func minTimeToType(word string) int {
    ans := len(word)
    a := rune('a')
    for _, c := range word {
        d := int(max(a-c, c-a))
        ans += min(d, 26-d)
        a = c
    }
    return ans
}

function minTimeToType(word: string): number {
    let a = 'a'.charCodeAt(0);
    let ans = word.length;
    for (const c of word) {
        const d = Math.abs(c.charCodeAt(0) - a);
        ans += Math.min(d, 26 - d);
        a = c.charCodeAt(0);
    }
    return ans;
}

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

题目描述

解法

方法一：贪心

评论