15 · ПРЕФИКСЫ

Trie

Префиксное дерево обменивает память на быстрый поиск строк и префиксов.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Узел

type Trie struct {
    next [26]*Trie
    word bool
}

Массив быстрее map для фиксированного маленького алфавита.

Индекс буквы

index := word[i] - 'a'

Результат byte подходит как индекс массива.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Добавление слова

Создаём отсутствующие рёбра.

O(length) time · O(length) space

solution.go

func (t *Trie) Insert(word string) {
    node := t
    for i := range word {
        index := word[i]-'a'
        if node.next[index] == nil { node.next[index] = &Trie{} }
        node = node.next[index]
    }
    node.word = true
}

ПРИМЕР РЕШЕНИЯ

Поиск префикса

Проходим по тем же рёбрам без проверки word.

O(length) time · O(1) space

solution.go

func (t *Trie) StartsWith(prefix string) bool {
    node := t
    for i := range prefix {
        node = node.next[prefix[i]-'a']
        if node == nil { return false }
    }
    return true
}

ПРИМЕР РЕШЕНИЯ

Поиск полного слова

После прохода по рёбрам дополнительно проверяем терминальный флаг.

O(length) time · O(1) space

solution.go

func (t *Trie) Search(word string) bool {
    node := t
    for i := range word {
        node = node.next[word[i]-'a']
        if node == nil { return false }
    }
    return node.word
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Фиксирован ли алфавит
Отделяй слово от его префикса
Для Unicode используй map[rune]*Trie