当前位置：首页 > news >正文

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

news 2026/7/31 5:16:07

【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 00到l e n ( w o r d ) − 1 len(word)-1len(word)−1遍历，第i ii个字母的按键次数为⌊ i 8 ⌋ + 1 \lfloor\frac{i}{8}\rfloor+1⌊8i⌋+1。

时间复杂度O ( l e n ( w o r d ) ) O(len(word))O(len(word))
空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-07-30 19:00:50 */classSolution{public:intminimumPushes(string&word){intans=0;for(inti=0,n=word.size();i<n;i++){ans+=i/8+1;}returnans;}};

解题方法二：if-else计算

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

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

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

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

时间复杂度O ( 1 ) O(1)O(1)，其实是log ⁡ 8 l e n ( w o r d ) \log_8 len(word)log8len(word)
空间复杂度O ( 1 ) O(1)O(1)

C++

/* * @LastEditTime: 2026-07-30 18:59:13 */classSolution{public:intminimumPushes(string&word){// 1-8: n// 9-16: 2n// 17-24: 3n// 25-26: 4nintn=word.size();intcnt=0;if(n<=8){returnn;}cnt+=8;if(n<=16){returncnt+(n-8)*2;}cnt+=8*2;if(n<=24){returncnt+(n-16)*3;}cnt+=8*3;returncnt+(n-24)*4;}};