Задача: Префиксное дерево

Условие: префиксное дерево - это структура данных для эффективного хранения и извлечения ключей в массиве строк. 

Необходимо реализовать класс со следующими методами:

- Trie() - инициализатор;

- void insert(String word) - осуществляет вставку в экземпляр класса;

- boolean search(String word) - возвращает флаг о наличии слова word в дереве;

- boolean startsWith(String prefix) - возвращает флаг о том, начинается ли слово, вставленное на предыдущем шаге с prefix.

Пример:

Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Вывод: [null, null, true, false, true, null, true]

Объяснение:

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple");  // return True

trie.search("app");   // return False

trie.startsWith("app"); // return True

trie.insert("app");

trie.search("app");   // return True

Решение :

Go

type Trie struct {
    children [26]*Trie
    isEnd bool
}


/** Initialize your data structure here. */
func Constructor() Trie {
    return Trie{}
}


/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
    curr := this
    for _, ch := range word {
        idx := ch - 'a'
        if curr.children[idx] == nil {
            curr.children[idx] = &Trie{}
        }
        curr = curr.children[idx]
    }
    curr.isEnd = true
}


/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    curr := this
    for _, ch := range word {
        idx := ch - 'a'
        if curr.children[idx] == nil {
            return false
        }
        curr = curr.children[idx]
    }
    return curr.isEnd
}


/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    curr := this
    for _, ch := range prefix {
        idx := ch - 'a'
        if curr.children[idx] == nil {
            return false
        }
        curr = curr.children[idx]
    }
    return true
}