Revising Tries

trie.go

package main

import (
	"encoding/json"
	"fmt"
)

func main() {
	t := NewTrie()
	t.Insert("name")
	t.Insert("noob")
	// fmt.Printf("trie %s", t.String())
	fmt.Printf("contains noob = %t", t.Contains("noobb"))
}

type Node struct {
	value       rune
	letters     map[rune]*Node
	isEndOfWord bool
}

func NewNode(val rune, isEndOfWord bool) *Node {
	return &Node{
		value:       val,
		letters:     make(map[rune]*Node, 0),
		isEndOfWord: isEndOfWord,
	}
}

type Trie struct {
	root *Node
}

func NewTrie() *Trie {
	return &Trie{
		root: &Node{
			value:       '\x00',
			letters:     make(map[rune]*Node, 0),
			isEndOfWord: false,
		},
	}
}

func (t *Trie) Insert(val string) {
	if len(val) == 0 {
		return
	}
	current := t.root

	for idx, v := range val {
		if current.letters[v] == nil {
			current.letters[v] = NewNode(v, idx == len(val)-1)
		}
		current = current.letters[v]

	}
}

func (t *Trie) Contains(word string) bool {
	if len(word) == 0 {
		return false
	}
	current := t.root

	for idx, val := range word {
    // check if the word is in the trie if not return false
		current = current.letters[val]
		if current == nil {
			return false
		}

		lastChar := idx == len(word)-1

    // check if the values are equal and we are the end of a word in the trie and this is the last character in the word
		if val == current.value && current.isEndOfWord && lastChar {
			return true
		}
	}

	return false
}