Implement Trie (Prefix Tree)

Q: Какова временная сложность префиксного дерева?

Вставка, поиск и startsWith проходят по одной ссылке на каждую букву, поэтому каждая операция занимает O(L) для слова длиной L независимо от количества сохранённых слов. Пространственная сложность составляет O(T) узлов для T вставленных букв в общей сложности; каждый узел хранит до 26 ссылок на дочерние узлы.

Q: Зачем использовать trie вместо хеш-множества?

Хеш-множество находит целые слова за O(L) , но не может ответить на вопрос о префиксе, не просканировав каждое слово. Хранение каждого префикса во втором множестве обходится в 210 букв для одного слова длиной 20 букв. Trie хранит каждый общий префикс один раз и отвечает на оба вопроса за один проход.

СреднеПрефиксное дерево

+10

Постройте бор (префиксное дерево) для слов в нижнем регистре с тремя операциями: insert w добавляет слово w, search w сообщает, было ли добавлено само слово w, а startsWith p сообщает, начинается ли какое-либо добавленное слово с p. Слово считается префиксом самого себя.

Операция i — это ops[i] для слова words[i]. Выполните их по порядку на пустом боре и верните по одной строке для каждой: "null" для операции вставки, "true" или "false" для операции поиска или startsWith.

Функция

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: операции в порядке их выполнения
wordsstring-array: слово или префикс для каждой операции
Возвращаетstring-array: по одному ответу на операцию, в виде текста

Ограничения

1 ≤ ops.length ≤ 2000
words.length == ops.length
Каждый ops[i] — это insert, search или startsWith.
1 ≤ words[i].length ≤ 20
words[i] содержит только строчные английские буквы.

Примеры

Ввод: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Вывод: ["null", "false", "true", "null", "true"]
Пояснение: car — начало card, поэтому startsWith car равно "true", но car никогда не добавляли, поэтому первый поиск возвращает "false". После insert car поиск находит его.

Ввод: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Вывод: ["null", "null", "true", "false", "false", "true", "true"]
Пояснение: Оба слова начинаются с te, но ни одно из них не совпадает в точности с te, поэтому startsWith равно "true", а search — "false". Ни одно слово не начинается с tex, а tea является префиксом самого себя.

Ввод: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Вывод: ["false", "false", "null", "true", "false", "true"]
Пояснение: В пустом боре оба запроса дают "false". После insert dog поиск находит это слово, ни одно слово не начинается с dogs, а do — начало слова dog.

Дополнительный вопрос

Как добавить операцию countPrefix p, которая возвращает количество различных сохранённых слов, начинающихся с p, по-прежнему за O(L) времени?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Хеш-множество поддерживает запрос search, но в нём нет понятия начала, поэтому startsWith будет просматривать каждое слово. В префиксном дереве каждое слово хранится как путь из букв от корня: слова с одинаковым началом проходят по общему пути, а флаг отмечает конец сохранённого слова. Для обоих запросов достаточно пройти по не более чем L связям.

Веди список слов и просматривай его

Идея

Храните каждое добавленное слово в списке. search w сравнивает w с каждым сохранённым словом, а startsWith p проверяет, начинается ли какое-либо сохранённое слово с p. Это правильно, потому что проверка напрямую соответствует определению. При n сохранённых словах каждый запрос требует до n сравнений длиной до L букв: 1 000 слов и 1 000 запросов дают миллион сравнений строк.

Алгоритм

Начните с пустого списка.
insert w: добавьте w.
search w: верните, есть ли сохранённое слово, равное w.
startsWith p: верните, начинается ли какое-нибудь сохранённое слово с p.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

Префиксное дерево: ссылки на дочерние узлы и флаг окончания

Идея

Каждый узел представляет один префикс — буквы на пути от корня до него. В нём есть ссылка на дочерний узел для каждой буквы, которая может идти следующей (26 ячеек или карта), и флаг isEnd, указывающий, заканчивается ли там в точности сохранённое слово. Вставка tea создаёт узлы для t, te и tea; вставка ten затем добавляет только ten, потому что у этих двух слов общий путь для te.

Путь, на котором встречается отсутствующая ссылка, доказывает, что ни одно сохранённое слово не начинается с этих букв: tex останавливается на te, у которого нет ссылки для x. Если путь доходит до конца, он заканчивается в узле, соответствующем запросу, поэтому startsWith возвращает true, а search отвечает значением флага. Узел для te существует, но его флаг выключен, поэтому search te возвращает false. Каждая операция проходит не более L ссылок независимо от количества сохранённых слов, а префиксное дерево содержит по одному узлу для каждого уникального префикса.

Алгоритм

Создай корень без дочерних ссылок и с выключенным isEnd.
insert w: от корня переходи по ссылке для каждой буквы, создавая узел, если он отсутствует. Установи isEnd для последнего узла.
find(p): от корня переходи по ссылке для каждой буквы; сразу возвращай отсутствие результата, если какой-либо ссылки нет, иначе возвращай достигнутый узел.
search w: возвращает true, когда find(w) возвращает узел с установленным isEnd.
startsWith p: возвращает true, когда find(p) возвращает узел.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Ловушки и крайние случаи

Разрешение search возвращать true всякий раз, когда путь существует. После insert card путь для car существует, но search car должен возвращать false.
Установка isEnd только у недавно созданных узлов. При вставке card после cards ничего не создаётся, но последнему узлу нужен этот флаг.
Создание нового дочернего узла, когда связь уже существует. Вставка ten с новым узлом t приводит к потере tea.
Чтение за концом пути. При startsWith sunny, когда сохранено только sun, нужно остановиться на первой отсутствующей связи и вернуть false.

Частые вопросы3

Какова временная сложность префиксного дерева?

Вставка, поиск и startsWith проходят по одной ссылке на каждую букву, поэтому каждая операция занимает O(L) для слова длиной L независимо от количества сохранённых слов. Пространственная сложность составляет O(T) узлов для T вставленных букв в общей сложности; каждый узел хранит до 26 ссылок на дочерние узлы.

Зачем использовать trie вместо хеш-множества?

Хеш-множество находит целые слова за O(L), но не может ответить на вопрос о префиксе, не просканировав каждое слово. Хранение каждого префикса во втором множестве обходится в 210 букв для одного слова длиной 20 букв. Trie хранит каждый общий префикс один раз и отвечает на оба вопроса за один проход.

Должен ли узел префиксного дерева использовать массив из 26 ссылок или хеш-таблицу?

Массив находит дочерний узел по одному индексу, но занимает 26 ячеек на узел, даже если у узла всего один дочерний узел. В карте хранятся только существующие дочерние узлы, и она подходит для любого алфавита, но требует хеш для каждой буквы. Для английских строчных букв подходят оба варианта; для Unicode или разреженных префиксных деревьев карта экономит память.

def trieOps(ops, words):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Ожидаемый вывод

["null", "false", "true", "null", "true"]