#3014
Minimum Number of Pushes to Type Word I
pupil · 330 · lc easy +22 · verified · 67% accepted · 196 likes · top 73%
Description
You are given a string word containing distinct lowercase English letters.
On a telephone keypad, keys 2–9 can be remapped to any collections of lowercase letters. Each letter must map to exactly one key. Pressing a key once gives the first letter, twice the second, and so on.
Return the minimum total key presses needed to type word after an optimal remapping.
Note: 1, *, #, and 0 do not map to any letters.
Example 1:
Input: word = "abcde"
Output: 5
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
Total cost is 1 + 1 + 1 + 1 + 1 = 5.
It can be shown that no other mapping can provide a lower cost.
Example 2:
Input: word = "xycdefghij"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> two pushes on key 2
"c" -> one push on key 3
"d" -> two pushes on key 3
"e" -> one push on key 4
"f" -> one push on key 5
"g" -> one push on key 6
"h" -> one push on key 7
"i" -> one push on key 8
"j" -> one push on key 9
Total cost is 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12.
It can be shown that no other mapping can provide a lower cost.
Code
1
2
3