题目描述
给你一个字符串 word
,由 不同 小写英文字母组成。
电话键盘上的按键与 不同 小写英文字母集合相映射,可以通过按压按键来组成单词。例如,按键 2
对应 ["a","b","c"]
,我们需要按一次键来输入 "a"
,按两次键来输入 "b"
,按三次键来输入 "c"
。
现在允许你将编号为 2
到 9
的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母,但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word
所需的 最少 按键次数。
返回重新映射按键后输入 word
所需的 最少 按键次数。
下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1
,*
,#
和 0
不 对应任何字母。
样例
输入:word = "abcde"
输出:5
解释:图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。
输入:word = "xyzxyzxyzxyz"
输出:12
解释:图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 3 上按一次
"z" -> 在按键 4 上按一次
总成本为 1 * 4 + 1 * 4 + 1 * 4 = 12 。
可以证明不存在其他成本更低的映射方案。
注意按键 9 没有映射到任何字母:不必让每个按键都存在与之映射的字母,但是每个字母都必须映射到按键上。
输入: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^5
word
仅由小写英文字母组成。
算法
(贪心) $O(n + |\Sigma| \log |\Sigma|)$
- 统计每种字母的出现次数,尽可能地让出现次数多的排到前面。
时间复杂度
- 需要 $O(n)$ 的时间统计每种字母的出现次数。
- 需要 $O(|\Sigma| \log |\Sigma|)$ 的时间排序出现次数。
- 最后仅需要常数的时间统计答案。
- 故总时间复杂度为 $O(n + |\Sigma| \log |\Sigma|)$。
空间复杂度
- 需要 $O(|\Sigma|)$ 的额外空间存储每种字母的出现次数。
C++ 代码
class Solution {
public:
int minimumPushes(string word) {
const int n = word.size();
vector<int> seen(26, 0);
for (char c : word)
++seen[c - 'a'];
sort(seen.begin(), seen.end());
int ans = 0;
for (int i = 25; i >= 18; i--) ans += seen[i];
for (int i = 17; i >= 10; i--) ans += 2 * seen[i];
for (int i = 9; i >= 2; i--) ans += 3 * seen[i];
for (int i = 1; i >= 0; i--) ans += 4 * seen[i];
return ans;
}
};