3014.输入单词需要的最少按键次数 I：遍历 / if-else计算(比纯数学公式写起来麻烦但好想)

【LetMeFly】3014.输入单词需要的最少按键次数 I：遍历 / if-else计算(比纯数学公式写起来麻烦但好想)

力扣题目链接：https://leetcode.cn/problems/minimum-number-of-pushes-to-type-word-i/

给你一个字符串 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个可用按键，分配按键时应该优先使用按1次的位置，分配完再分配按2次的位置，…。

解题方法一：遍历

从$0$到$len(word)-1$遍历，第$i$个字母的按键次数为$\lfloor\frac{i}{8}\rfloor+1$。

• 时间复杂度$O(len(word))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-07-30 19:00:50
 */
class Solution {
public:
    int minimumPushes(string& word) {
        int ans = 0;
        for (int i = 0, n = word.size(); i < n; i++) {
            ans += i / 8 + 1;
        }
        return ans;
    }
};

解题方法二：if-else计算

如果字母个数为1-8, 则每个字母只需要按一次；

否则（先分配8个字母共计需要按8次）如果字母个数为9-16, 则第9-16个字母需要按两次；

否则（再分配8个需要按两次的字母）如果字母个数为17-24, 则第17-24个字母需要按三次；

否则（再分配8个需要按三次的字母），第25-n个字母需要按四次。

• 时间复杂度$O(1)$，其实是$\log_8 len(word)$
• 空间复杂度$O(1)$

C++

/*
 * @LastEditTime: 2026-07-30 18:59:13
 */
class Solution {
public:
    int minimumPushes(string& word) {
        // 1-8: n
        // 9-16: 2n
        // 17-24: 3n
        // 25-26: 4n
        int n = word.size();
        int cnt = 0;
        if (n <= 8) {
            return n;
        }
        cnt += 8;
        if (n <= 16) {
            return cnt + (n - 8) * 2;
        }
        cnt += 8 * 2;
        if (n <= 24) {
            return cnt + (n - 16) * 3;
        }
        cnt += 8 * 3;
        return cnt + (n - 24) * 4;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源