LeetCode 筆記 - 820. Short Encoding of Words

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 820. Short Encoding of Words

給定一個字串清單，請給出合法的編碼字串長度

解題思維

這題編碼規則可以先仔細看一下題目

根據規則，words = [“time”, “me”, “bell”]
其中 me 可以包含在 time 裏面，所以合法的編碼字串就變成 time#bell#

所以我們拿到一個字串 x 其實就是檢查 x# 有沒有已經在答案裡面
沒有就加上去

那要達到這樣的效果，勢必比較大的字串需要先出現在答案裡面
所以需要先 Sorting 一下

程式碼

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        
        words.sort(key=len, reverse=True)
        
        ans = ''
        for x in words:
            if (target := f"{x}#") not in ans:
                ans = f"{ans}{target}"
        return len(ans)

👌

也許你也會想看看

LeetCode 筆記 - 2075. Decode the Slanted Ciphertext
LeetCode 筆記 - 318. Maximum Product of Word Lengths
LeetCode 筆記 - 647. Palindromic Substrings