LeetCode 1974: Minimum Time to Type Word Using Special Typewriter (Circular Distance Greedy)
LeetCode 1974StringGreedyToday we solve LeetCode 1974 - Minimum Time to Type Word Using Special Typewriter.
Source: https://leetcode.com/problems/minimum-time-to-type-word-using-special-typewriter/
English
Problem Summary
You have a circular typewriter with lowercase letters a..z. The pointer starts at 'a'. Rotating one step clockwise or counterclockwise costs 1 second, and typing the current letter costs 1 second. Return the minimum total time to type word.
Key Insight
For two letters on a 26-letter circle, the best rotation is the shorter path between clockwise distance and counterclockwise distance.
Algorithm (Greedy Per Character)
1) Keep current pointer letter cur (start at 'a').
2) For each target letter ch, compute d = abs(ch - cur).
3) Rotation cost is min(d, 26 - d).
4) Add rotation cost + 1 typing second, then set cur = ch.
Complexity Analysis
Time: O(n) where n = word.length.
Space: O(1).
Common Pitfalls
- Forgetting that the keyboard is circular (26 - d) can be better than d.
- Forgetting to add the typing cost (+1) for each character.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int minTimeToType(String word) {
int ans = 0;
char cur = 'a';
for (char ch : word.toCharArray()) {
int d = Math.abs(ch - cur);
ans += Math.min(d, 26 - d); // rotate
ans += 1; // type
cur = ch;
}
return ans;
}
}
func minTimeToType(word string) int {
ans := 0
cur := byte('a')
for i := 0; i < len(word); i++ {
ch := word[i]
d := int(ch - cur)
if d < 0 {
d = -d
}
if 26-d < d {
d = 26 - d
}
ans += d + 1
cur = ch
}
return ans
}
class Solution {
public:
int minTimeToType(string word) {
int ans = 0;
char cur = 'a';
for (char ch : word) {
int d = abs(ch - cur);
ans += min(d, 26 - d); // rotate
ans += 1; // type
cur = ch;
}
return ans;
}
};
class Solution:
def minTimeToType(self, word: str) -> int:
ans = 0
cur = 'a'
for ch in word:
d = abs(ord(ch) - ord(cur))
ans += min(d, 26 - d) # rotate
ans += 1 # type
cur = ch
return ans
var minTimeToType = function(word) {
let ans = 0;
let cur = 'a';
for (const ch of word) {
let d = Math.abs(ch.charCodeAt(0) - cur.charCodeAt(0));
d = Math.min(d, 26 - d);
ans += d + 1;
cur = ch;
}
return ans;
};
中文
题目概述
有一个环形打字机，字符是 a..z。指针初始在 'a'。每转动一格耗时 1 秒（顺/逆时针都可以），按下当前字符也耗时 1 秒。求输入字符串 word 的最短总时间。
核心思路
两个字符在 26 个字母构成的圆环上，最短移动距离是“正向距离”和“反向距离”中的较小值。
算法步骤（逐字符贪心）
1）维护当前指针字符 cur（初始为 'a'）。
2）对每个目标字符 ch，计算 d = abs(ch - cur)。
3）旋转成本是 min(d, 26 - d)。
4）加上旋转成本和输入成本 +1，然后更新 cur = ch。
复杂度分析
时间复杂度：O(n)，其中 n = word.length。
空间复杂度：O(1)。
常见陷阱
- 忘记环形特性：有时 26 - d 比 d 更短。
- 忘记每输入一个字符都要额外 +1 秒。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int minTimeToType(String word) {
int ans = 0;
char cur = 'a';
for (char ch : word.toCharArray()) {
int d = Math.abs(ch - cur);
ans += Math.min(d, 26 - d); // rotate
ans += 1; // type
cur = ch;
}
return ans;
}
}
func minTimeToType(word string) int {
ans := 0
cur := byte('a')
for i := 0; i < len(word); i++ {
ch := word[i]
d := int(ch - cur)
if d < 0 {
d = -d
}
if 26-d < d {
d = 26 - d
}
ans += d + 1
cur = ch
}
return ans
}
class Solution {
public:
int minTimeToType(string word) {
int ans = 0;
char cur = 'a';
for (char ch : word) {
int d = abs(ch - cur);
ans += min(d, 26 - d); // rotate
ans += 1; // type
cur = ch;
}
return ans;
}
};
class Solution:
def minTimeToType(self, word: str) -> int:
ans = 0
cur = 'a'
for ch in word:
d = abs(ord(ch) - ord(cur))
ans += min(d, 26 - d) # rotate
ans += 1 # type
cur = ch
return ans
var minTimeToType = function(word) {
let ans = 0;
let cur = 'a';
for (const ch of word) {
let d = Math.abs(ch.charCodeAt(0) - cur.charCodeAt(0));
d = Math.min(d, 26 - d);
ans += d + 1;
cur = ch;
}
return ans;
};
Comments