M3016.输入单词需要的最少按键次数 II

https://leetcode.cn/problems/minimum-number-of-pushes-to-type-word-ii/

greedy, 给你一个字符串 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 = "xyzxyzxyzxyz"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 3 上按一次
"z" -> 在按键 4 上按一次
总成本为 1 * 4 + 1 * 4 + 1 * 4 = 12 。
可以证明不存在其他成本更低的映射方案。
注意按键 9 没有映射到任何字母：不必让每个按键都存在与之映射的字母，但是每个字母都必须映射到按键上。

示例 3：

输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
"f" -> 在按键 7 上按一次
"g" -> 在按键 8 上按一次
"h" -> 在按键 9 上按两次
"i" -> 在按键 9 上按一次
总成本为 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24 。
可以证明不存在其他成本更低的映射方案。

提示：

1 <= word.length <= 10^5
word 仅由小写英文字母组成。

这道题可以使用贪心算法来解决。

解题思路

按键机制分析：
- 电话键盘上只有 2 到 9 共 8 个可用按键。
- 每个按键可以映射多个字母：
  - 按键上的第 1 个字母，输入成本为 1 次按键。
  - 按键上的第 2 个字母，输入成本为 2 次按键。
  - 按键上的第 3 个字母，输入成本为 3 次按键。
  - 按键上的第 4 个字母，输入成本为 4 次按键。
- 也就是说：
  - 最多有 8 个字母可以享受 1 次按键成本（每个按键放 1 个）。
  - 接下来最多有 8 个字母可以享受 2 次按键成本（每个按键放第 2 个）。
  - 接下来最多有 8 个字母可以享受 3 次按键成本（每个按键放第 3 个）。
  - 剩余字母（最多 2 个，因为英文字母一共 26 个）成本为 4 次按键。
贪心策略：
- 出现的频率越高的字母，越应该放在按键的前面，即赋予更低的按键成本。
- 因此，我们只需要统计 word 中各个字母出现的频次，将其降序排序。
- 前 8 个高频字母的成本为 1，接下来的 8 个字母成本为 2，再接下来的 8 个成本为 3，以此类推。

Python 代码实现

python

from collections import Counter


class Solution:

    def minimumPushes(self, word: str) -> int:
        # 1. 统计每个字母出现的频次
        counts = Counter(word)

        # 2. 将频次按照降序排列
        sorted_counts = sorted(counts.values(), reverse=True)

        total_pushes = 0

        # 3. 遍历频次计算总按键次数
        for i, count in enumerate(sorted_counts):
            # i // 8 + 1 计算当前字母需要的按键次数：
            # 下标 0~7  : 按 1 次
            # 下标 8~15 : 按 2 次
            # 下标 16~23: 按 3 次
            # 下标 24~25: 按 4 次
            pushes = (i // 8) + 1
            total_pushes += count * pushes

        return total_pushes

复杂度分析

时间复杂度： $O (N)$ ，其中 $N$ 是字符串 word 的长度。
- 统计字符串频率需要 $O (N)$ 时间。
- 不同的字母种类最多只有 $26$ 个，对最多 $26$ 个数进行排序的时间复杂度为 $O (1)$ 。
- 遍历数组也是最多 $26$ 次，复杂度为 $O (1)$ 。
- 综上，整体时间复杂度为 $O (N)$ 。
空间复杂度： $O (1)$ 。
- 哈希表和频次数组的大小最多为 $26$ ，只需要常数级别的额外空间。

M3016.输入单词需要的最少按键次数 II ​

M3016.输入单词需要的最少按键次数 II