// Online Go compiler to run Golang program online
// Print "Try programiz.pro" message

package main
import "fmt"

type TrieNode struct {
    children [26]*TrieNode
    isWord bool
}

type Trie struct {
	root *TrieNode
}

func Constructor() Trie {
    return Trie{
        root: &TrieNode{},
    }
}

func (this *Trie) Insert(word string) {
    current := this.root
    for _, letter := range word {
        position := letter-'a'
        if current.children[position] == nil {
            current.children[position] = new(TrieNode)
        }
        current = current.children[position]
    }
    current.isWord = true
}

func (this *Trie) Search(word string) bool {
    current := this.root
    for _, letter := range word {
        position := letter-'a'
        if current.children[position] == nil {
            return false
        }
        current = current.children[position]
    }

    if current != nil{
        return false
    } else {
        current.isWord = true
        return true
    }
}

func (this *Trie) StartsWith(prefix string) bool {
    current := this.root
    for _, letter := range prefix {
        position := letter-'a'
        if current.children[position] == nil {
            return false
        }
        current = current.children[position]
    }
    current.isWord = true
    return true
}



func main() {
  fmt.Println("run!")
  obj := Constructor()
  word := "apple"
  obj.Insert(word)
  out := obj.Search("apple")
  fmt.Println(out)
}