題目連結:
題目意譯:
一個字詞陣列 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。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。