LeetCode 题解工作台
输入单词需要的最少按键次数 I
给你一个字符串 word ，由 不同 小写英文字母组成。 电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"] ，我们需要按一次键来输入 "a" ，按两次键来输入 "b" ，按三次键来输入 "c" 。 现在允许你将编号为 2 …
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们注意到，字符串 中的所有字母都是不同的，因此，我们贪心地将字母均匀地分配到 个按键上，即可使得按键次数最少。 时间复杂度 $O(n / 8)$，其中 是字符串 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个字符串 word，由 不同 小写英文字母组成。
电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。
现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母，但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。
返回重新映射按键后输入 word 所需的 最少 按键次数。
下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不 对应任何字母。
示例 1：
输入：word = "abcde" 输出：5 解释：图片中给出的重新映射方案的输入成本最小。 "a" -> 在按键 2 上按一次 "b" -> 在按键 3 上按一次 "c" -> 在按键 4 上按一次 "d" -> 在按键 5 上按一次 "e" -> 在按键 6 上按一次 总成本为 1 + 1 + 1 + 1 + 1 = 5 。 可以证明不存在其他成本更低的映射方案。
示例 2：
输入：word = "xycdefghij" 输出：12 解释：图片中给出的重新映射方案的输入成本最小。 "x" -> 在按键 2 上按一次 "y" -> 在按键 2 上按两次 "c" -> 在按键 3 上按一次 "d" -> 在按键 3 上按两次 "e" -> 在按键 4 上按一次 "f" -> 在按键 5 上按一次 "g" -> 在按键 6 上按一次 "h" -> 在按键 7 上按一次 "i" -> 在按键 8 上按一次 "j" -> 在按键 9 上按一次 总成本为 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12 。 可以证明不存在其他成本更低的映射方案。
提示：
1 <= word.length <= 26word仅由小写英文字母组成。word中的所有字母互不相同。
解题思路
方法一：贪心
我们注意到，字符串 中的所有字母都是不同的，因此，我们贪心地将字母均匀地分配到 个按键上，即可使得按键次数最少。
时间复杂度 ，其中 是字符串 的长度。空间复杂度 。
class Solution:
def minimumPushes(self, word: str) -> int:
n = len(word)
ans, k = 0, 1
for _ in range(n // 8):
ans += k * 8
k += 1
ans += k * (n % 8)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) for sorting letters and O(n) for allocation and calculation, giving overall O(n log n). Space complexity is O(n) for storing letter counts and key mappings. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate immediately suggests a greedy allocation based on letter positions.
- question_mark
Mentions invariant that each letter must map to exactly one key.
- question_mark
Calculates total presses incrementally to check minimal mapping correctness.
常见陷阱
外企场景- error
Forgetting that each key can hold multiple letters and miscounting pushes.
- error
Assigning letters without respecting one-to-one key-letter mapping.
- error
Assuming sequential key mapping without sorting or prioritizing letter positions.
进阶变体
外企场景- arrow_right_alt
Minimize pushes when some keys have fixed letters and cannot be remapped.
- arrow_right_alt
Consider words with repeated letters, adjusting greedy allocation accordingly.
- arrow_right_alt
Use weighted letters where some letters cost more per press, adapting the greedy strategy.