Home
GoLang: Implement Trie (Prefix Tree)
Tags:, ,

GoLang: Implement Trie (Prefix Tree)

June 16, 2021 No Comments algorithms, data structure, Go Programming

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.

1
2
3
4
5
6
7
8
9
10
11

type Trie struct {
    children[26] *Trie
    isLeaf bool
}
 
/** Initialize your data structure here. */
func Constructor() Trie {
    var obj = Trie{}
    obj.isLeaf = false
    return obj
}
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/** 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);
 */
/** 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:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
473 words
Last Post: Teaching Kids Programming - Binary Tree Inorder Traversal via Recursion or Iteration
Next Post: Teaching Kids Programming - Back Tracking Algorithm to Generate Parentheses

The Permanent URL is: GoLang: Implement Trie (Prefix Tree)

Related posts:

  1. Unix Path Resolution Algorithm Given a Unix path, represented as a list of strings, return its resolved version. In...
  2. How to Monitor the CPU Temperature of Raspberry PI using Python Script? Raspberry PI does not have any fans – although you can either install cooling chips...
  3. The Algorithm to Make Words Bold in HTML Given a set of keywords words and a string S, make all appearances of all...
  4. Recursive Algorithm to Compute the Linked List Jumps You are given a singly linked list node containing positive integers. Return the same linked...
  5. How to Get Passive Income using the Spare CPU to Mine? You might wonder that: without Powerful GPU Graphic Cards, could I earn some passive income...
  6. Teaching Kids Programming – Remove Digit From Number to Maximize Result Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a string number...
  7. C++ Chess Board Printing in Windows Using CodePage 437 – Extended ASCII Well, most people, when they start programming in C/C++, they would like to print something...
  8. The MySQL If and Case Statement Exercise: How to Swap Elements in MySQL? Given a table salary, such as the one below, that has m=male and f=female values....

Leave a Reply