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 中的所有字母都不相同

提示：

  • 总共有 8 个按键。我们可以用每个按键按一次输入 8 个字符，用每个按键按两次输入 8 个不同的字符，以此类推。
  • 最优方法是将字母均匀地映射到按键上。

解题思路

这是一个贪心算法问题。关键在于理解题目的本质：

问题分析：

  • 我们有 8 个可用按键（2-9）
  • 每个按键可以映射任意数量的字母
  • 按键上第 k 个位置的字母需要按 k 次才能输入
  • 目标是最小化总按键次数

解题思路： 由于所有字母都是不同的，我们只需要考虑字母的总数量，而不需要考虑字母的出现频率。

最优策略是将字母尽可能均匀地分配到 8 个按键上：

  1. 前 8 个字母各放在一个按键的第一个位置（按 1 次）
  2. 接下来 8 个字母各放在一个按键的第二个位置（按 2 次）
  3. 以此类推…

算法实现： 对于长度为 n 的字符串，我们可以直接计算：

  • 前 8 个字母贡献：min(8, n) × 1
  • 第 9-16 个字母贡献：min(8, max(0, n-8)) × 2
  • 第 17-24 个字母贡献：min(8, max(0, n-16)) × 3
  • 第 25-26 个字母贡献：max(0, n-24) × 4

这可以简化为一个循环计算。

代码实现

class Solution {
public:
    int minimumPushes(string word) {
        int n = word.length();
        int result = 0;
        int pos = 0;
        
        while (pos < n) {
            int count = min(8, n - pos);
            int pushes = pos / 8 + 1;
            result += count * pushes;
            pos += 8;
        }
        
        return result;
    }
};

class Solution:
    def minimumPushes(self, word: str) -> int:
        n = len(word)
        result = 0
        pos = 0
        
        while pos < n:
            count = min(8, n - pos)
            pushes = pos // 8 + 1
            result += count * pushes
            pos += 8
        
        return result

public class Solution {
    public int MinimumPushes(string word) {
        int n = word.Length;
        int result = 0;
        int pos = 0;
        
        while (pos < n) {
            int count = Math.Min(8, n - pos);
            int pushes = pos / 8 + 1;
            result += count * pushes;
            pos += 8;
        }
        
        return result;
    }
}

var minimumPushes = function(word) {
    const n = word.length;
    let result = 0;
    let pos = 0;
    
    while (pos < n) {
        const count = Math.min(8, n - pos);
        const pushes = Math.floor(pos / 8) + 1;
        result += count * pushes;
        pos += 8;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(1)
空间复杂度O(1)

说明：

  • 时间复杂度：虽然有循环，但最多只会执行 4 次（因为最多 26 个字母，26/8 ≈ 3.25），所以是常数时间
  • 空间复杂度：只使用了常数个变量，空间复杂度为常数级别

相关题目