前往
大廳
主題

LeetCode - 820. Short Encoding of Words 解題心得

Not In My Back Yard | 2023-05-05 12:00:01 | 巴幣 0 | 人氣 145

題目連結:


題目意譯:
一個字詞陣列 words 的一個合法編碼為任何一個參考字串 s 以及一個索引值陣列 indices,使得
words.length == indices.length
該參考字串 s 以 '#' 字元作為結尾。
對於每一個索引值 indices[i],從 indices[i] 開始一路到下一個 '#' 字元(不包含該字元)形成的 s 之子字串等於 words[i]。

給定陣列 words,回傳在 words 所有可能的合法編碼中最短的參考字串 s 之長度。

限制:
1 ≦ words.length ≦ 2000
1 ≦ words[i].length ≦ 7
words[i] 只由小寫字母組成。



範例測資:
範例 1:
輸入: words = ["time", "me", "bell"]
輸出: 10
解釋: 一個合法的編碼可以是 s = "time#bell#" 而 indices = [0, 2, 5]。
words[0] = "time",從 indices[0] = 0 開始一路到下一個 '#' 字元形成的 s 之子字串,在 "time#bell#" 中以底線標示。
words[1] = "me",從 indices[1] = 2 開始一路到下一個 '#' 字元形成的 s 之子字串,在 "time#bell#" 中以底線標示。
words[2] = "bell",從 indices[2] = 5 開始一路到下一個 '#' 字元形成的 s 之子字串,在 "time#bell#" 中以底線標示。

範例 2:
輸入: words = ["t"]
輸出: 2
解釋: 一個合法的編碼可以是 s = "t#" 而 indices = [0]。


解題思維:
可以看到如果有一個字串 s 是另一個字串 t 的一個後綴(Suffix),也就是說存在一個索引值 i,使得 t[i] ~ t[t.length - 1] 這段子字串恰好為 s 的話,則在編碼中我們只需要放入 t 而不需要放入 s(因為對於 s,其編碼已經被包在 t 之中了)。

因此我們可以把所有是另一個字串的後綴之字串全部去除(可以單純用迴圈判斷,也可以用雜湊表(Hash Table)來做)。

假設最後剩下 C 個字串,則編碼的最小長度即為「這 C 個字串的長度」 + C。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作