2416. Sum of Prefix Scores of Strings
給一個有n個字串的矩陣words
當words[i]的任何prefix match到words[j]的prefix
i可以等於j
那麼分數就可以+1
請回傳經過上述操作的scores矩陣
思路:
將words裡所有的字串建立到一個字典樹裡
並且每到一個字母，那個字母的分數就+1
最後將每個words[i]去跑一下字典樹並且把分數加起來就好
沒什麼難度
golang cdoe :
type trie struct {
child [26]*trie
cnt int
}
func sumPrefixScores(words []string) []int {
tree := trie{[26]*trie{}, 0}
for _, val := range words {
insert(val, &tree)
}
res := make([]int, len(words))
for key, val := range words {
res[key] = search(val, &tree)
}
return res
}
func insert(s string, tree *trie) {
n := len(s)
for i := 0; i < n; i++ {
idx := int(s[i] - 'a')
if tree.child[idx] == nil {
tree.child[idx] = &trie{[26]*trie{}, 1}
} else {
tree.child[idx].cnt++
}
tree = tree.child[idx]
}
}
func search(s string, tree *trie) int {
n := len(s)
res := 0
for i := 0; i < n; i++ {
idx := int(s[i] - 'a')
if tree.child[idx] == nil {
break
}
res += tree.child[idx].cnt
tree = tree.child[idx]
}
return res
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.33.38 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727266342.A.7F5.html