Leetcode Note: Go - Most Common Word
Most Common Word - LeetCode
https://leetcode.com/problems/most-common-word/
- Go 言語で取り組んだメモ
所感
- string 配列 banned と string 変数 paragraph が渡される
- paragraph に含まれる banned 以外の頻出頻度が最も高い単語を string で return する
回答
Most Common Word - LeetCode
https://leetcode.com/problems/most-common-word/solution/
100% Idiomatic Go solution using Trie - LeetCode Discuss
https://leetcode.com/problems/most-common-word/discuss/1058262/100-Idiomatic-Go-solution-using-Trie
type Trie struct {
Children [26]*Trie
IsBanned bool
Count int
}
func mostCommonWord(paragraph string, banned []string) string {
root := &Trie{}
for _, word := range banned {
node := insertWord(root, word)
node.IsBanned = true
}
paragraph = strings.ToLower(paragraph)
words := strings.FieldsFunc(paragraph, func(c rune) bool {
return !unicode.IsLetter(c)
})
result, max := "", 0
for _, word := range words {
if node := insertWord(root, word); !node.IsBanned {
node.Count++
if node.Count > max {
result, max = word, node.Count
}
}
}
return result
}
func insertWord(root *Trie, word string) *Trie {
for i := 0; i < len(word); i++ {
idx := word[i] - 'a'
if root.Children[idx] == nil {
root.Children[idx] = &Trie{}
}
root = root.Children[idx]
}
return root
}