LeetCode 筆記 - 820. Short Encoding of Words

Posted on

題目在此 820. Short Encoding of Words

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

解題思維

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

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

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

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

程式碼

1
2
3
4
5
6
7
8
9
10
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)

👌

也許你也會想看看