Greedy策略: 讓總按鍵次數最少 Min Num of Push to Type Word II_LC #3016

Ahmed Helal on Unsplash

題目敘述: Minimum Number of Pushes to Type Word II

給定一個傳統手機鍵盤，如圖所示

接著給定一個字串word。

現在讓你重新安排每個字母的所在位置，每個字母可以重新安排到2~9這幾個鍵盤上的位置，每個字母限定只能選擇一個數字鍵去對應。

請問重新安排之後，最少要按幾次鍵盤才能輸出給定的字串word?

測試範例

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 = "xyzxyzxyzxyz"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> one push on key 3
"z" -> one push on key 4
Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12
It can be shown that no other mapping can provide a lower cost.
Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.

Example 3:

重新安排後的鍵盤最佳配置

Input: word = "aabbccddeeffgghhiiiiii"
Output: 24
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
"f" -> one push on key 7
"g" -> one push on key 8
"h" -> two pushes on key 9
"i" -> one push on key 9
Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24.
It can be shown that no other mapping can provide a lower cost.

約束條件

Constraints:

• 1 <= word.length <= 10^5

輸入字串長度介於1~十萬。

• word consists of lowercase English letters.

輸入字串只會有小寫英文字母。

觀察 如何讓按鍵次數變少?

直覺的想法就是，

讓最頻繁使用到的字元放到第一排，接著放頻率次高的，依此類推，

最後才放頻率最低的到最後一排。

演算法 Greedy策略，根據出現次數進行最佳化

承接觀察點的思考，先建立一個字典，統計每個英文字母的出現次數。

接著進行排序，讓前8個出現次數最高的優先排在第一排，接著放8個次高到第二排，...，依此類推。

核心觀念:用最小的成本(按鍵次數)去服務最常用到的英文字母！

程式碼 Greedy策略，根據出現次數進行最佳化

class Solution:
    def minimumPushes(self, word: str) -> int:
        
        # a list of occurrences of characters
        occurrence = list( Counter(word).values() )

        # Keep in descending order from high frequency to low frequency
        occurrence.sort(reverse = True)

        # First 8 high frequency characters put on first level
        # Second 8 high frequency characters put on second level
        # ... and so on
        return sum( occ * (i // 8 + 1) for i, occ in enumerate(occurrence) )

複雜度分析

時間複雜度: O(n)

掃描輸入字串的每個字元，耗時O(n)

這個案例中，排序的成本反而比較小 = O(26 log 26) = O(1) = 常數級別

空間複雜度: O(1)

建立字典所需空間最大為O(26) = O(1) = 小寫英文字母的數量

Reference:

[1] Minimum Number of Pushes to Type Word II - LeetCode