E3014.输入单词需要的最少按键次数 I

greedy, https://leetcode.cn/problems/minimum-number-of-pushes-to-type-word-i/

给你一个字符串 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 <= 26
• word 仅由小写英文字母组成。
• word 中的所有字母互不相同。

这道题可以通过贪心策略来求解。

解题思路

1. 分析题目：

   • 题目保证字符串 word 中的所有字母互不相同（每个字母出现频率均为 1）。
   • 共有 8 个 可用按键（编号 2 到 9）。
   • 每个按键可以分配多个字母：
     • 排在按键第 1 位置的字母，需要按 1 次；
     • 排在按键第 2 位置的字母，需要按 2 次；
     • 排在按键第 3 位置的字母，需要按 3 次；
     • 排在按键第 4 位置的字母，需要按 4 次。

2. 贪心选择：

   • 为了使总按键次数最少，我们应当优先把字母分配到 8 个按键的第 1 位置。
   • 如果字母数量超过 8 个，多出来的字母再分配到 8 个按键的第 2 位置，以此类推。

3. 规律推导：

   • 对于第 $i$ 个字母（下标从 $0$ 开始，范围为 $0\le i<\text{len}(word)$）：
     • 第 $0\sim 7$ 个字母（前 8 个）：需要按 1 次，即 0 // 8 + 1 = 1；
     • 第 $8\sim 15$ 个字母（中 8 个）：需要按 2 次，即 8 // 8 + 1 = 2；
     • 第 $16\sim 23$ 个字母：需要按 3 次，即 16 // 8 + 1 = 3；
     • 第 $24\sim 25$ 个字母：需要按 4 次，即 24 // 8 + 1 = 4。
   • 因此，第 $i$ 个字母所需的按键次数为：(i // 8) + 1。

---

Python 代码实现

class Solution:
    def minimumPushes(self, word: str) -> int:
        # 对于第 i 个字符，其按键次数为 (i // 8) + 1
        return sum((i // 8) + 1 for i in range(len(word)))

---

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为字符串 word 的长度。因为 $n\le 26$，所以实际运行时间为常数级别 $\mathcal{O}(1)$。
• 空间复杂度：$\mathcal{O}(1)$，仅使用了常数空间的变量。