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

标签: 贪心 数学 字符串

难度: Easy

给你一个字符串 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 中的所有字母互不相同。

Submission

运行时间: 19 ms

内存: 15.9 MB

class Solution:
    def minimumPushes(self, word: str) -> int:
        nums={}
        for w in word:
            nums.setdefault(w,0)
            nums[w]+=1
        nums=nums.values()
        # print(nums)
        nums=sorted(nums,reverse=True)
        ans=0
        for i in range(0,len(nums)):
            ans+=nums[i]*i//8+1
        return ans

Explain

该题目的核心思想是重新映射电话键盘上的按键到字母，以使得输入给定的单词所需的按键次数最小。解题步骤如下： 1. 统计单词中每个字母的出现频率。 2. 将频率按从高到低排序，因为频率高的字母应尽可能放在按键次数少的位置上。 3. 计算按键次数：由于题目没有明确按键上字母的数量限制，理论上可以假设每个按键上可以放无限多的字母。但由于每个按键的按键次数是有限的，我们需要将出现次数高的字母尽量分配给按键次数少的位置（例如，按键'2'上的第一个位置）。为了达到这个目的，对于每个字母，按其在排序后的位置计算需要的按键次数，即位置除以8（因为一个按键最多有8个位置）加1。 这种方法利用了贪心的策略，即优先考虑频率高的字母，以减少总的按键次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumPushes(self, word: str) -> int:
        # 统计每个字母的出现次数
        nums = {}
        for w in word:
            nums.setdefault(w, 0)
            nums[w] += 1
        # 获取频率列表并按降序排序
        nums = sorted(nums.values(), reverse=True)
        ans = 0
        # 计算每个字母需要的按键次数
        for i in range(len(nums)):
            ans += (nums[i] * (i // 8) + 1)
        return ans

Explore

选择按字母的出现频率进行降序排序是因为我们希望频率高的字母能够尽可能使用较少的按键次数输入，即将频率最高的字母映射到按键次数最少的位置。这种方法基于贪心算法的原理，通过优化每一步的选择来尽量减少总的按键次数，从而达到整体的最优解。

公式 `(i // 8 + 1)` 用于计算每个字母所需的按键次数。这里的数字 `8` 代表的是一个假定情况，即每个按键最多可以映射8个不同的字母。因此，`i // 8` 计算的是字母在排序后的列表中属于哪一个按键（每8个字母一个周期），而 `+1` 是因为按键次数从1开始计数。这是一种简化的假设，实际上可以根据具体情况调整这个数字，以适应不同的按键和字母映射策略。

尽管每个按键可以映射任意数量的字母，但我们需要确保每个字母恰好映射到一个按键上以满足题目要求。这可以通过为每个字母分配一个唯一的按键来实现。在实际操作中，可以通过创建一个映射表，将每个字母映射到一个具体的按键编号上。这个过程需要确保每个字母都被映射一次，而没有一个字母被映射到多个按键或者一个按键映射多个相同的字母。