Implement Trie (Prefix Tree)

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

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

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

+10

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

Операции передаются в порядке следования в виде ops, а words[i] — это слово или префикс для ops[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"]
Пояснение: Сначала хранится только card, поэтому поиск по car возвращает "false": это слово никогда не добавляли. Это начало слова card, поэтому startsWith car возвращает "true". После добавления 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, поэтому startsWith te — это "true", но ни одно слово не состоит точно из te, поэтому поиск не удаётся. Ни одно слово не начинается с tex. Было вставлено ten, а tea является префиксом самого себя, поэтому последние два ответа — "true".

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

+16 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

Храните список слов и просматривайте его

Идея

Храните каждое добавленное слово в списке. Для search w сравнивайте w с каждым сохранённым словом. Для startsWith p проверяйте, начинается ли какое-либо сохранённое слово с p. Во втором примере startsWith te сначала проверяет tea и на этом останавливается; для ответа "false" запросу startsWith tex нужно проверить оба слова.

Это работает, и при заданных ограничениях алгоритм завершается, но каждый запрос проверяет все сохранённые слова. Если сохранено n слов, запрос требует до n сравнений длиной до L букв каждое. 1 000 сохранённых слов и 1 000 запросов — это миллион сравнений строк, а объём работы продолжает расти вместе со словарём. Кроме того, общие части не используются повторно: для tea и ten отдельно хранятся t и e.

Алгоритм

Начни с пустого списка слов.
Для 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, который показывает, заканчивается ли сохранённое слово именно в этом узле.

insert проходит по слову от корня. Для каждой буквы он переходит по ссылке на дочерний узел, предварительно создавая узел, если ссылки нет, а на последней букве устанавливает isEnd. Во втором примере вставка tea создаёт узлы для t, te и tea и помечает tea. Вставка ten повторно использует t и te и добавляет только ten. У этих двух слов общий путь для te, откуда и появилось название «префиксное дерево».

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

Именно флаг отличает слово от префикса. В первом примере после вставки card существует путь c, a, r. Без флага search car ошибочно вернул бы true. Последующая вставка car вообще не создаёт узлов — она только включает флаг.

Каждая операция проходит не более чем по L ссылкам, где L — длина слова, поэтому её стоимость составляет O(L) независимо от количества сохранённых слов. В префиксном дереве хранится по одному узлу для каждого уникального префикса; их количество никогда не превышает общего числа вставленных букв.

Алгоритм

Определи узел со ссылками на дочерние узлы (26 ячеек или карту) и флагом isEnd, затем создай пустой корень.
Для insert w: начиная с корня, переходи по ссылке для каждой буквы w, создавая узел, если ссылка отсутствует. Установи isEnd на последнем узле.
Напиши вспомогательную функцию find(p): начиная с корня, переходи по ссылке для каждой буквы p и прекращай поиск, как только ссылка отсутствует. Верни достигнутый узел.
Для search w: дай ответ true, если find(w) достигает узла, у которого установлен isEnd.
Для startsWith p: дай ответ true, если find(p) достигает узла.
Выполни операции по порядку и запиши "null", "true" или "false" для каждой.

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 всякий раз, когда путь существует. После вставки card путь для car существует, но car никогда не вставляли.
Устанавливать isEnd только у вновь созданных узлов. При вставке card после cards ничего не создаётся, но последнему узлу всё равно нужен этот флаг.
Создавать новый дочерний узел, даже если связь уже существует. Это отсекает всё, что хранится ниже него: вставка ten с новым узлом t приводит к потере tea.
Забывать, что слово является префиксом самого себя. После вставки tea startsWith tea возвращает true.
Продолжать чтение после конца пути. Префикс, который длиннее любого слова, например sunny, если хранится только sun, должен остановиться на первой отсутствующей связи и вернуть false.
Возвращать логические значения или не включать вставки в ответ. Для каждой операции нужна одна строка, в том числе "null" для вставки.

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

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

Insert, search и StartsWith переходят по одной ссылке на каждую букву аргумента, поэтому каждая из этих операций выполняется за время O(L) для слова длиной L, независимо от количества сохранённых слов. В префиксном дереве хранится не более одного узла на каждую вставленную букву, поэтому для T вставленных букв требуется O(T) узлов, а каждый узел хранит до 26 ссылок на дочерние узлы.

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

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

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

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

Где на практике используются префиксные деревья?

Автодополнение и поисковые подсказки проходят по префиксу, который вы ввели, в структуре trie и выводят слова, начинающиеся с него. Проверки орфографии, словесные игры, в которых ищут слова из словаря на игровом поле, и маршрутизаторы, которые находят самый длинный совпадающий префикс адреса, используют ту же структуру. Trie подходит всякий раз, когда у множества строк совпадает начало и вы выполняете поиск по началу.

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

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