Learning GoLang: Implement Trie (Prefix Tree)

justyy (84)in #programming • 5 years ago

Trie aka Prefix Tree is a data structure helps to search a word or prefix in a list of strings. The following declars the struct (class) type of Trie Node in GoLang.

type Trie struct {
    children[26] *Trie
    isLeaf bool
}

/** Initialize your data structure here. */
func Constructor() Trie {
    var obj = Trie{}
    obj.isLeaf = false
    return obj
}

Given the input is lowercase or upper characters, we can use a static array of size 26 to store the references (pointers) to children Trie Node. Howerver, we can also use hash map if there are any other characters.

For Trie Node, we usually need to implement the Search, Prefix, and Insert function. They all require walking down the path of Trie.

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
    var cur = this
    for _, ch := range word {
        var idx = ch - 'a'
        if cur.children[idx] == nil {
            cur.children[idx] = &Trie{}
        }
        cur = cur.children[idx]
    }
    cur.isLeaf = true
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    var cur = this
    for _, ch := range word {
        var idx = ch - 'a'
        if cur.children[idx] == nil {
            return false
        }
        cur = cur.children[idx]
    }
    return cur.isLeaf
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    var cur = this
    for _, ch := range prefix {
        var idx = ch - 'a'
        if cur.children[idx] == nil {
            return false
        }
        cur = cur.children[idx]
    }
    return true
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

Trie Algorithms Implementations:

Reposted to Blog