trie

Documentation

Overview

Effecient Trie data structure implementation using a map.

It can store all UTF-8 characters in runes as supported in golang.package trie

Index

• type Trie
  • func NewTrie() *Trie
  • func (t *Trie) Exists(word string) bool
  • func (t *Trie) Insert(words ...string)
  • func (t *Trie) Nodes() int
  • func (t *Trie) Size() int
  • func (t *Trie) SortedWords() []string
  • func (t *Trie) Suggestions(query string) []string
  • func (t *Trie) Words() []string

Types

type Trie

type Trie struct {
	// contains filtered or unexported fields
}

Trie holds the data in a prefix tree using an unordered map

func NewTrie

func NewTrie() *Trie

initializes a new Trie

func (*Trie) Exists

func (t *Trie) Exists(word string) bool

Returns true if word exists in the trie.

O(m) time complexity

func (*Trie) Insert

func (t *Trie) Insert(words ...string)

Insert one or more words into the Tri.

Insertion is O(m) where m is the number of letters in the word.

func (*Trie) Nodes

func (t *Trie) Nodes() int

Returns the number of nodes in the trie

func (*Trie) Size

func (t *Trie) Size() int

Returns the number of words in the trie.

func (*Trie) SortedWords

func (t *Trie) SortedWords() []string

Returns a slice of words sorted alphabetically

func (*Trie) Suggestions

func (t *Trie) Suggestions(query string) []string

Returns a slice of words matching query from the trie. Worst case: O(m+n) where m is the number of characters in query and n is the number of nodes in the trie.

func (*Trie) Words

func (t *Trie) Words() []string

Returns all words in the trie in no particular order.