package main

import (
	"fmt"
	"unicode"
)

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

type Trie struct {
	root TrieNode
}

func (t *Trie) Add(s string) {
	node := &t.root
	for _, r := range s {
		if unicode.IsLower(r) {
			i := r - 'a'
			if node.children[i] == nil {
				node.children[i] = &TrieNode{}
			}
			node = node.children[i]
		} else {
			panic("only lowercase letters are allowed")
		}
	}
	node.isEndOfWord = true
}

func (t *Trie) Has(s string) bool {
	node := &t.root
	for _, r := range s {
		if unicode.IsLower(r) {
			i := r - 'a'
			if node.children[i] == nil {
				return false
			}
			node = node.children[i]
		} else {
			panic("only lowercase letters are allowed")
		}
	}
	return node.isEndOfWord
}

func (t *Trie) All() []string {
	var traverse func(*TrieNode, string) []string
	traverse = func(node *TrieNode, s string) []string {
		var result []string
		if node.isEndOfWord {
			result = append(result, s)
		}
		for i, c := range node.children {
			if c != nil {
				result = append(result, traverse(c, string(append([]rune(s), rune('a'+i))))...)
			}
		}
		return result
	}
	return traverse(&t.root, "")
}

func main() {
	t := &Trie{}
	t.Add("hello")
	t.Add("world")
	t.Add("hell")
	fmt.Println(t.All())
	fmt.Println(t.Has("hell"))
}