LeetCode 筆記 - 820. Short Encoding of Words

題目在此 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)

👌

也許你也會想看看