Medium

题目描述

给你一个字符串 word，其中包含小写英文字母。

电话键盘上的按键映射到不同的小写英文字母集合，可以通过按压按键来组成单词。例如，按键 2 映射到 [“a”,“b”,“c”]，我们需要按一次来输入 “a”，按两次来输入 “b”，按三次来输入 “c”。

可以将编号为 2 到 9 的按键重新映射到不同的字母集合。按键可以映射到任意数量的字母，但每个字母必须恰好映射到一个按键上。你需要找到输入字符串 word 所需的最少按键次数。

返回重新映射按键后输入 word 所需的最少按压次数。

示例 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

示例 3：

输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释：重新映射的键盘提供最小代价。
总代价是 24。

约束：

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

解题思路

这是一个典型的贪心算法问题。我们需要最小化总的按键次数，关键是理解按键的分配策略。

核心思路：

  1. 我们有8个可用的按键（2-9），每个按键可以映射多个字母
  2. 在同一个按键上，第1个字母需要按1次，第2个字母需要按2次，以此类推
  3. 为了最小化总按键次数，应该把出现频率最高的字母放在最容易按到的位置

算法步骤：

  1. 统计每个字母的出现频率
  2. 将字母按频率从高到低排序
  3. 贪心分配：前8个字母各占一个按键的第1位（按1次），接下来8个字母各占一个按键的第2位（按2次），以此类推
  4. 计算总的按键次数

时间复杂度分析：

  • 统计频率：O(n)
  • 排序：O(26log26) = O(1)，因为字母数量固定
  • 计算结果：O(26) = O(1)
  • 总体：O(n)

这种贪心策略是正确的，因为我们总是优先给频率高的字母分配更少的按键次数。

代码实现

class Solution {
public:
    int minimumPushes(string word) {
        vector<int> freq(26, 0);
        for (char c : word) {
            freq[c - 'a']++;
        }
        
        sort(freq.rbegin(), freq.rend());
        
        int result = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0) break;
            int pushes = i / 8 + 1;
            result += freq[i] * pushes;
        }
        
        return result;
    }
};

class Solution:
    def minimumPushes(self, word: str) -> int:
        from collections import Counter
        
        freq = Counter(word)
        sorted_freq = sorted(freq.values(), reverse=True)
        
        result = 0
        for i, count in enumerate(sorted_freq):
            pushes = i // 8 + 1
            result += count * pushes
        
        return result

public class Solution {
    public int MinimumPushes(string word) {
        int[] freq = new int[26];
        foreach (char c in word) {
            freq[c - 'a']++;
        }
        
        Array.Sort(freq, (a, b) => b.CompareTo(a));
        
        int result = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0) break;
            int pushes = i / 8 + 1;
            result += freq[i] * pushes;
        }
        
        return result;
    }
}

var minimumPushes = function(word) {
    const freq = new Array(26).fill(0);
    for (const c of word) {
        freq[c.charCodeAt(0) - 97]++;
    }
    
    freq.sort((a, b) => b - a);
    
    let result = 0;
    for (let i = 0; i < 26; i++) {
        if (freq[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
统计字母频率O(n)O(1)
排序频率数组O(1)O(1)
计算最少按键次数O(1)O(1)
总体O(n)O(1)

其中 n 是字符串 word 的长度。空间复杂度为 O(1) 是因为字母种类固定为 26 个。

相关题目