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

标签: 贪心 哈希表 字符串 计数 排序

难度: Medium

给你一个字符串 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 <= 105
  • word 仅由小写英文字母组成。

Submission

运行时间: 96 ms

内存: 16.5 MB

class Solution:
    def minimumPushes(self, word: str) -> int:
        nums = []
        for c in range(26):
            cnt = word.count(chr(97 + c))
            if cnt > 0:
                nums.append(cnt)
        ans = 0
        nums.sort(key = lambda x: -x)
        i = 2
        cnt = 1
        for x in nums:
            ans += cnt * x
            i += 1
            if i == 10:
                cnt += 1
                i = 2
        return ans

Explain

首先，对于输入字符串 word，统计每个字母出现的次数。然后，按照出现次数从大到小排序这些统计结果。为了最小化总的按键次数，应该将出现次数最多的字母映射到按键次数最少的按键上，即每个按键的第一个位置。一旦按键 2 到 9 的第一个位置都被占用后，再从按键 2 开始，将出现次数较多的字母映射到第二个位置，以此类推。这种策略保证了高频字母使用较少的按键次数，从而实现总按键次数的最小化。

时间复杂度: O(n)

空间复杂度: O(1)

# 添加了注释的代码

class Solution:
    def minimumPushes(self, word: str) -> int:
        nums = []
        # 统计每个字母的出现次数
        for c in range(26):
            cnt = word.count(chr(97 + c))
            if cnt > 0:
                nums.append(cnt)
        # 初始化答案
        ans = 0
        # 按字母出现次数从大到小排序
        nums.sort(key = lambda x: -x)
        i = 2  # 从按键2开始
        cnt = 1  # 初始每个按键按一次
        # 分配每个字母到一个按键
        for x in nums:
            ans += cnt * x  # 计算总按键次数
            i += 1
            # 如果所有按键的当前位置被占满，移动到下一个位置
            if i == 10:
                cnt += 1
                i = 2
        return ans

Explore

在算法实现中，通过逐个将字母的出现次数从大到小排序，并依次映射到按键的位置上，确保了每个字母只映射到一个按键位置。然而，每个按键可以映射到多个字母，这是通过遍历排序后的字母出现次数列表，并在按键按满当前位置后，通过增加按键次数（cnt变量）并重置按键位置（i变量）到2来实现的，从而让每个按键可以循环使用，映射到不同的字母。

算法通过对每个字母的出现次数进行统计，并只将出现次数大于0的字母加入到计算列表中。对于未出现的字母，因为它们的出现次数为0，所以在统计过程中被忽略，不会被加入到计算列表中，因此这些字母不会影响最终的按键次数计算。

在典型的手机键盘布局中，按键2到9是用于输入字母的按键。按键1通常用于特殊字符或其他功能，而0按键也通常用于空格或特殊功能，因此在此类算法中常从按键2开始映射字母。这样的选择是基于实际手机键盘的布局，确保映射方案的实用性和直观性。