https://leetcode.com/problems/sum-of-prefix-scores-of-strings/description/
給定一個大小為 n
的字串陣列 words
,其中每個字串都是非空的
我們定義字串 term
的分數為滿足 term
是 words[i]
的前綴字串的字串數量
例如,若 words = ["a", "ab", "abc", "cab"]
,則 "ab"
的分數是 2,因為 "ab"
是 "ab"
和 "abc"
的前綴字串
回傳一個大小為 n
的陣列 answer
,其中 answer[i]
是 words[i]
的每個非空前綴字串的分數總和
注意:
這題看到 prefix of string 我們多少應該會想到 Trie
沒錯,我們可以使用 Trie 的概念來解這題
不過我們沒有需要查找一個詞,我們只需要累計出他的分數就好
使用 Trie 能更便利我們聯想到解法
不過我們其實還能從中再得到一些啟發
Trie 做的其實可以理解成基於前綴的分類
那其實,我們依據字典順序做排序,不也是能達到分類嗎?
例如 words = ["abc","ab","bc","b"]
經過排序後應該會是 sorted_words = ["ab", "abc", "b", "bc"]
你會發現前綴有 "ab"
的字串會被排在一起
這就衍伸出第二種演算法
我們使用 DP 的方式來解題
假設有兩個字串 跟 他們在字典順序上是相鄰的
令 表示到第 個字母為止 跟 的共同前綴長
則我們可以得到:
但這樣就算把所有 j
的情況都掃過一輪,我們仍未解決這個題目,需要反轉順序後再執行一遍上述檢查
簡單理解就是目前我們只有由前往後看,還需要由後往前看回來,得到的 ans[i]
才會是雙向互看的結果
否則會發現有些情況會漏算
最後不要忘了,字串被認為是它自己的前綴字串 😉
algo 2 本質上還是跟 algo 1 做類似的事情,卻換來了是時間空間上的節省
雖然比較不好懂,但以執行結果來說,algo 2 的成績明顯好很多
algo 1 的缺點很明顯,我們的資料結構不但會花更多的 Memory ,而且我們需要花時間建立,之後才能再遍歷一次字串算成績
這樣的做法屬於依賴資料結構的特性