[Toggle Comments]
package trie // file: ./trie/trie.go type Trie struct { root *node } // time: O(m), where m is the word length; space: O(m) func (t Trie) Insert(word string) { n := t.root for _, r := range word { if !n.Contains(r) { n.Put(r, NewNode()) } n = n.Get(r) } n.MarkEnd() } func (t Trie) searchPrefix(prefix string) *node { n := t.root for _, r := range prefix { if !n.Contains(r) { return nil } n = n.Get(r) } return n } // time: O(m), where m is the prefix length; space: O(1) func (t Trie) StartsWith(prefix string) bool { node := t.searchPrefix(prefix) return node != nil } // time: O(m), where m is the prefix length; space: O(1) func (t Trie) Search(prefix string) bool { node := t.searchPrefix(prefix) return node != nil && node.end } // time: O(m), where m is the length of the `initial` string. // space: O(S), where S is the number of all characters in all strings. func (t Trie) SearchLongestPrefix(initial string) string { result := []rune{} n := t.root for _, r := range initial { // If the node has more than one child, then all the children constitute // longer distinct words; there is no common prefix from that point on. // // (f) // / // (i) // / \ // (z) (t) // // If you take the above prefix tree, it branches off after (i). Thus, // it is impossible for “fiz” and “fit” to have a common prefix larger // than “fi”. // // If the node has zero children, it’s an end node, which ends our // search, and we can break too. if n.Count() != 1 { break } // If the node does not have the current rune, it’s as far as // we can get—we bail out. if !n.Contains(r) { break } // If the node is marked as the end of “any” word, then any common // prefix cannot be longer than that. So we will break the loop // here too. if n.end { break } // If none of the above cases happen, then our rune is part of the // common prefix; we append it to the result and proceed with the // next node, which we will compare with the next rune of the string // `initial` in the next iteration of this loop. result = append(result, r) n = n.Get(r) } // The common prefix that we’ve found so far. return string(result) } func New() *Trie { return &Trie{root: NewNode()} } /* * \ * \\, * \\\,^,.,,. Zero to Hero * ,;7~((\))`;;,, <zerotohero.dev> * ,(@') ;)`))\;;', stay up to date, be curious: learn * ) . ),(( ))\;, * /;`,,/7),)) )) )\,, * (& )` (,((,((;( ))\, */