Design Add and Search Words Data Structure

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

Добавление слова длины L занимает O(L) , как и поиск без точек, независимо от того, сколько слов сохранено. В худшем случае поиск с d точками занимает O(26^d · L) . Для хранения T добавленных букв требуется O(T) узлов.

СреднеПрефиксное дерево Поиск с возвратом

+10

Создайте словарь слов с двумя операциями. addWord w сохраняет слово w. search p проверяет, совпадает ли какое-либо сохранённое слово с шаблоном p: длина должна быть одинаковой, и в каждой позиции шаблон содержит ту же букву или точку ., которая обозначает любую одну букву.

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

Функция

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

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

Ограничения

1 ≤ ops.length ≤ 2500
words.length == ops.length
Каждый ops[i] — это addWord или search.
1 ≤ words[i].length ≤ 20
Слово, которое нужно добавить, содержит только строчные английские буквы.
Шаблон для поиска содержит строчные английские буквы и не более 3 точек.

Примеры

Ввод: ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Вывод: ["null", "null", "true", "false", "false", "true"]
Пояснение: r.se соответствует обоим словам: точка заменяет o в rose и i в rise. Точка никогда не обозначает отсутствующую букву, поэтому ros и rose. не соответствуют. Шаблон ..s. соответствует, поскольку в обоих словах s стоит на третьем месте.

Ввод: ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
Вывод: ["false", "null", "true", "true", "false"]
Пояснение: Словарь изначально пуст, поэтому ... ничего не находит. После добавления sky и ..., и s.y совпадают с ним, а sk слишком короткий.

Ввод: ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
Вывод: ["null", "null", "true", "false", "true"]
Пояснение: Первая точка в ma..o может быть буквой p в maple или буквой n в mango; слово maple заканчивается на e, но mango подходит. Ни одно слово не заканчивается на y, поэтому m...y не подходит, а m.p.e соответствует слову maple.

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

Как бы ты расширил search, если бы шаблон мог также содержать *, обозначающую любую последовательность букв, в том числе пустую?

Подсказки

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

Открыто 0 из 3

Решение

Точка означает, что поиск не может указать нужное ему слово: ma..o соответствует 676 возможным словам, и важны только те, что сохранены. В префиксном дереве слова с одинаковым началом идут по одному пути. Буква в шаблоне ведёт по одной ссылке, точка разветвляет поиск только по существующим дочерним узлам, а поиск в глубину возвращается из тупиковых ветвей.

Сравните шаблон с каждым сохранённым словом

Идея

Храни добавленные слова в списке и проверяй каждое из них по шаблону: одинаковая длина, а в каждой позиции — точка или та же буква. Это и есть определение совпадения; проверяй его для каждого сохранённого слова, чтобы получить правильный ответ.

Каждый поиск проверяет весь список: O(n·L) для n слов длиной до L букв, даже если в шаблоне нет точки. 1,250 добавлений, за которыми следуют 1,250 поисков, проверят 1,250 × 1,250 = 1,562,500 слов.

Алгоритм

Храни добавленные слова в списке. Для addWord w добавь w и запиши "null".
Для search p сравнивай p с каждым словом той же длины, позицию за позицией, считая, что точка подходит к любой букве.
При первом совпадении запиши "true", а если совпадений нет — "false".

def matches(pattern, word):
    # Same length, and every position holds a dot or the same letter.
    if len(pattern) != len(word):
        return False
    for p, w in zip(pattern, word):
        if p != "." and p != w:
            return False
    return True


def wordDictionaryOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            stored.append(word)
            result.append("null")
        else:
            found = any(matches(word, s) for s in stored)
            result.append("true" if found else "false")
    return result

Префиксное дерево с поиском в глубину по точкам

Идея

Помести слова в префиксное дерево: rose и rise используют общий узел r, затем разветвляются на o и i. Флаг конца отмечает каждый узел, в котором заканчивается сохранённое слово. Последовательность букв — это один путь по префиксному дереву. Точка может обозначать любую букву, поэтому при встрече точки попробуй каждую существующую дочернюю ветвь и верни true, как только одна из них приведёт к совпадению.

Для ma..o у узла для ma есть дочерние узлы p и n. Через p вторая точка ведёт к l, у которого нет дочернего узла o, поэтому поиск возвращается назад и пробует n: g, затем o, где заканчивается mango.

Для совпадения нужно пройти весь шаблон и оказаться в узле с флагом, что определяет длину: ros останавливается на узле без флага, а rose. заканчивается на узле без дальнейших переходов. Точка открывает не более 26 ветвей, поэтому d точек посещают не более 26^d · L узлов, а шаблон без точек требует O(L).

Алгоритм

У каждого узла есть ссылки на дочерние узлы и флаг окончания, изначально выключенный.
Для addWord w: проходите по w от корня, создавая недостающие узлы, и устанавливайте флаг окончания там, где проход останавливается.
match(node, i): если i равно длине шаблона, верните флаг окончания узла.
Если p[i] — буква, верните false, если дочерний узел отсутствует, иначе match(child, i+1). Если это точка, верните true, если для любого существующего дочернего узла выполняется match(child, i+1), иначе false.
Для каждого поиска записывайте match(root, 0), для каждого добавления — "null".

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


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

    def add_word(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 search(self, pattern):
        return self._match(self.root, pattern, 0)

    def _match(self, node, pattern, i):
        # Can the path below node spell pattern[i:] and end on a stored word?
        if i == len(pattern):
            return node.is_end
        ch = pattern[i]
        if ch == ".":
            # A dot stands for any letter: try each child until one works.
            for child in node.children.values():
                if self._match(child, pattern, i + 1):
                    return True
            return False
        child = node.children.get(ch)
        return child is not None and self._match(child, pattern, i + 1)


def wordDictionaryOps(ops, words):
    dictionary = WordDictionary()
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            dictionary.add_word(word)
            result.append("null")
        else:
            result.append("true" if dictionary.search(word) else "false")
    return result

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

Позволять первому потомку определять результат для точки. В ma..o ветвь p завершается неудачей, а ветвь n — успешно, поэтому код, возвращающий результат первого потомка, отвечает false, если сначала проверяет p. Отвечайте false, только если не сработал ни один потомок.
Отвечать true, когда шаблон заканчивается на любом узле. После добавления rose ros достигает узла, но ни одно слово на нём не заканчивается. Проверьте флаг конца.
Позволять точке соответствовать отсутствующей букве. card. соответствует cards, но не card.
Считать точку буквой. Обращение к элементу массива из 26 ячеек по индексу '.' - 'a' выходит за границы массива, поэтому сначала проверьте, является ли символ точкой.

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

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

Добавление слова длины L занимает O(L), как и поиск без точек, независимо от того, сколько слов сохранено. В худшем случае поиск с d точками занимает O(26^d · L). Для хранения T добавленных букв требуется O(T) узлов.

Можешь решить эту задачу с помощью хеш-множества вместо префиксного дерева?

Да, но с компромиссами. Множество позволяет найти совпадение с шаблоном без точек за один поиск. Если в шаблоне есть точки, придётся либо проверить каждое сохранённое слово такой длины — O(n·L), либо подставить вместо каждой точки все 26 букв и проверить каждый результат: 17 576 поисков для трёх точек.

Поиск в префиксном дереве должен быть рекурсивным или итеративным?

Подойдут оба варианта. Рекурсия проходит по одному уровню на каждую букву шаблона, здесь не более 20, поэтому стек вызовов остаётся небольшим. В итеративном варианте используется стек пар (node, position), и при встрече точки в него добавляется каждый дочерний узел.

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

Тест #1

Тест #2

Тест #3

Аргументы

ops = ["addWord", "addWord", "search", "search", "search", "search"]
words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]

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

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