main.go

package main

import "fmt"

func findWord(start, cursor *Trie, s, currentWord string, words []string) ([]string, error) {
	if s == "" {
		if cursor.Word {
			return append(words, currentWord), nil
		}
		//Didn't end with a word in our list
		return nil, fmt.Errorf("last string was not a word")
	}
	if cursor.Word {
		w, err := findWord(start, start, s, "", append(words, currentWord))
		if err == nil {
			return w, nil
		}
	}

	child, exist := cursor.Children[s[0]]
	if !exist {
		return nil, fmt.Errorf("Current word does not exist")
	}
	currentWord = currentWord + string(s[0])
	return findWord(start, child, s[1:len(s)], currentWord, words)

}

func main() {
	// words := []string{"quick", "brown", "the", "fox"}
	words := []string{"bed", "bath", "bedbath", "and", "beyond"}
	// str := "thequickbrownfox"
	str := "bedbathandbeyond"

	t := New()
	for _, word := range words {
		t.AddWord(word)
	}

	words, err := findWord(t, t, str, "", []string{})
	fmt.Println(words, err)
}


type Trie struct {
	Children map[byte]*Trie
	Word     bool
}

func New() *Trie {
	return &Trie{
		Children: map[byte]*Trie{},
	}
}

func (T *Trie) AddWord(word string) {
	if word == "" {
		T.Word = true
		return
	}
	c, present := T.Children[word[0]]
	if !present {
		T.Children[word[0]] = New()
		c = T.Children[word[0]]
	}
	c.AddWord(word[1:len(word)])
}