Easy

题目描述

有一个特殊的打字机，小写英文字母 ‘a’ 到 ‘z’ 按圆形排列，带有一个指针。只有当指针指向某个字符时，才能输入该字符。指针初始指向字符 ‘a’。

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

  • 将指针沿逆时针或顺时针方向移动一个字符
  • 输入指针当前指向的字符

给定一个字符串 word，返回输入 word 中所有字符所需的最少秒数。

示例 1：

输入：word = "abc"
输出：5
解释：
字符按以下方式输入：
- 在 1 秒内输入字符 'a'，因为指针初始在 '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 <= word.length <= 100
  • word 由小写英文字母组成

提示：

  • 移动到下一个字母时只有两个可能的方向
  • 移动到下一个字母时，总是选择耗时最少的方向

解题思路

这是一道模拟题，关键在于理解圆形排列的特性和最优移动策略。

核心思路：

  1. 圆形距离计算：26个字母组成圆环，从字母 a 到字母 b 有两种移动方式：

    • 顺时针：(b - a + 26) % 26 步
    • 逆时针：(a - b + 26) % 26 步
    • 选择较短的路径：min(顺时针, 逆时针)

  2. 贪心策略：对于每一步移动，都选择最短路径，这样能保证总时间最少。

  3. 时间计算：

    • 移动时间：当前位置到目标位置的最短距离
    • 输入时间：每个字符都需要 1 秒输入
    • 总时间 = 所有移动时间 + 字符个数

算法流程：

  1. 初始化当前位置为 ‘a’，总时间为 0
  2. 遍历目标单词的每个字符
  3. 计算从当前位置到目标字符的最短移动时间
  4. 累加移动时间和输入时间（1秒）
  5. 更新当前位置为目标字符

这种贪心策略是正确的，因为每一步都选择局部最优解（最短路径），而圆形结构保证了局部最优就是全局最优。

代码实现

class Solution {
public:
    int minTimeToType(string word) {
        int time = 0;
        char current = 'a';
        
        for (char target : word) {
            int clockwise = (target - current + 26) % 26;
            int counterclockwise = (current - target + 26) % 26;
            time += min(clockwise, counterclockwise) + 1;
            current = target;
        }
        
        return time;
    }
};

class Solution:
    def minTimeToType(self, word: str) -> int:
        time = 0
        current = 'a'
        
        for target in word:
            clockwise = (ord(target) - ord(current) + 26) % 26
            counterclockwise = (ord(current) - ord(target) + 26) % 26
            time += min(clockwise, counterclockwise) + 1
            current = target
        
        return time

public class Solution {
    public int MinTimeToType(string word) {
        int time = 0;
        char current = 'a';
        
        foreach (char target in word) {
            int clockwise = (target - current + 26) % 26;
            int counterclockwise = (current - target + 26) % 26;
            time += Math.Min(clockwise, counterclockwise) + 1;
            current = target;
        }
        
        return time;
    }
}

var minTimeToType = function(word) {
    let time = 0;
    let current = 'a';
    
    for (let target of word) {
        const clockwise = (target.charCodeAt(0) - current.charCodeAt(0) + 26) % 26;
        const counterclockwise = (current.charCodeAt(0) - target.charCodeAt(0) + 26) % 26;
        time += Math.min(clockwise, counterclockwise) + 1;
        current = target;
    }
    
    return time;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n为单词长度，需要遍历每个字符一次
空间复杂度O(1)只使用了常量级别的额外空间

相关题目