Implement Trie (Prefix Tree)

1. Problem Description

Implement a Trie (prefix tree) with the three operations insert, search, and startsWith.

2. Approach

• tree

3. Implementation

package main

type node struct {
	m     map[rune]*node
	isEnd bool
}

func newNode() *node {
	return &node{
		m:     make(map[rune]*node, 0),
		isEnd: false}
}

type Trie struct {
	root *node
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{root: newNode()}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	runes := []rune(word)
	current := this.root
	for _, r := range runes {
		n, ok := current.m[r]
		if !ok {
			n = newNode()
			current.m[r] = n
		}
		current = n
	}
	current.isEnd = true
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	runes := []rune(word)
	current := this.root
	for _, r := range runes {
		current = current.m[r]
		if current == nil {
			return false
		}
	}

	return current.isEnd
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	runes := []rune(prefix)
	current := this.root
	for _, r := range runes {
		current = current.m[r]
		if current == nil {
			return false
		}
	}

	return current != nil
}

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

4. References

• 208. Implement Trie (Prefix Tree) - LeetCode