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

题目描述

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

解法

方法一：贪心 + 排序

我们用一个哈希表或数组 $cnt$ 统计字符串 $word$ 中每个字母出现的次数。接下来，按照字母出现的次数从大到小排序，然后每 $8$ 个字母一组，将每组中的字母分配到 $8$ 个按键上。

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = Counter(word)
        ans = 0
        for i, x in enumerate(sorted(cnt.values(), reverse=True)):
            ans += (i // 8 + 1) * x
        return ans

class Solution {
    public int minimumPushes(String word) {
        int[] cnt = new int[26];
        for (int i = 0; i < word.length(); ++i) {
            ++cnt[word.charAt(i) - 'a'];
        }
        Arrays.sort(cnt);
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            ans += (i / 8 + 1) * cnt[26 - i - 1];
        }
        return ans;
    }
}

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

func minimumPushes(word string) (ans int) {
    cnt := make([]int, 26)
    for _, c := range word {
        cnt[c-'a']++
    }
    sort.Ints(cnt)
    for i := 0; i < 26; i++ {
        ans += (i/8 + 1) * cnt[26-i-1]
    }
    return
}

function minimumPushes(word: string): number {
    const cnt: number[] = Array(26).fill(0);
    for (const c of word) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    cnt.sort((a, b) => b - a);
    let ans = 0;
    for (let i = 0; i < 26; ++i) {
        ans += (((i / 8) | 0) + 1) * cnt[i];
    }
    return ans;
}

function minimumPushes(word) {
    const cnt = Array(26).fill(0);
    for (const c of word) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    cnt.sort((a, b) => b - a);
    let ans = 0;
    for (let i = 0; i < 26; ++i) {
        ans += (((i / 8) | 0) + 1) * cnt[i];
    }
    return ans;
}

方法二：优先队列（大根堆）

TypeScriptJavaScript

function minimumPushes(word: string): number {
    const pq = new MaxPriorityQueue();
    const cnt = new Map<string, number>();
    let [i, res] = [0, 0];

    for (const x of word) {
        cnt.set(x, (cnt.get(x) ?? 0) + 1);
    }

    for (const [x, c] of cnt) {
        pq.enqueue(x, c);
    }

    while (!pq.isEmpty()) {
        const c = pq.dequeue().priority;
        res += c * (((i++ / 8) | 0) + 1);
    }

    return res;
}

function minimumPushes(word) {
    const pq = new MaxPriorityQueue();
    const cnt = new Map();
    let [i, res] = [0, 0];

    for (const x of word) {
        cnt.set(x, (cnt.get(x) ?? 0) + 1);
    }

    for (const [x, c] of cnt) {
        pq.enqueue(x, c);
    }

    while (!pq.isEmpty()) {
        const c = pq.dequeue().priority;
        res += c * (((i++ / 8) | 0) + 1);
    }

    return res;
}

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

题目描述

解法

方法一：贪心 + 排序

方法二：优先队列（大根堆）

评论