Разработка структуры данных добавления и поиска слов: Leetcode 211 ⇐ Python
-
Anonymous
Разработка структуры данных добавления и поиска слов: Leetcode 211
В настоящее время я пытаюсь решить проблему добавления и поиска структуры данных слов в leetcode. Вопрос в следующем:
Разработайте структуру данных, которая поддерживает добавление новых слов и поиск строка соответствует любой ранее добавленной строке.
Реализовать класс WordDictionary:
WordDictionary() Инициализирует объект.
void addWord(word) Добавляет word в структуру данных, его можно сопоставить позже.
bool search(word) Возвращает true, если в структуре данных есть какая-либо строка, которая соответствует word или false в противном случае. слово может содержать точки ., где точки могут быть соответствует любой букве.
Моя стратегия:
Моя стратегия предполагает представление дерева с помощью хэш-карты вместо традиционной древовидной структуры на основе связанных списков, стремясь к повышению производительности и снижению сложности. Используя хэш-карту, мы можем быстро получить доступ к следующему узлу, не проходя через ненужные узлы, что ускоряет операции, особенно с большими наборами данных.
Например, при вставке в эту структуру таких слов, как «яблоко» и «приложение», она организуется как вложенные хэш-карты, где каждый символ в слове указывает на другую хэш-карту, представляющую следующий символ. Конец слова отмечается специальной парой ключ-значение {'end': {}}. Таким образом, мы эффективно сохраняем и ищем слова с минимальной пространственной и временной сложностью.
Мой код:
класс WordDictionary(объект): защита __init__(сам): self.map = {} Защиту addWord(я, слово): """ :введите слово: ул :rtype: Нет """ текущий = self.map для меня в слове: если я в текущем: ток = ток[я] еще: текущий [я] = {} ток = ток[я] текущий['конец'] = {} возвращаться def search(сам, слово): """ :введите слово: ул :rtype: бул """ текущий = self.map для меня в слове: если я в текущем: ток = ток[я] элиф я == '.': текущий = {ключ: значение для d в current.values() для ключа, значение в d.items()} еще: вернуть ложь если «конец» в текущем: вернуть истину вернуть ложь Решение кажется эффективным в большинстве случаев, но я столкнулся с ошибкой в тестовом примере 16, который не дает правильного результата. Из-за длины тестового примера 16 особенно сложно определить, где происходит ошибка. Мне нужны советы, как найти и исправить эту логическую ошибку. Сможете ли вы помочь во всем разобраться?
В настоящее время я пытаюсь решить проблему добавления и поиска структуры данных слов в leetcode. Вопрос в следующем:
Разработайте структуру данных, которая поддерживает добавление новых слов и поиск строка соответствует любой ранее добавленной строке.
Реализовать класс WordDictionary:
WordDictionary() Инициализирует объект.
void addWord(word) Добавляет word в структуру данных, его можно сопоставить позже.
bool search(word) Возвращает true, если в структуре данных есть какая-либо строка, которая соответствует word или false в противном случае. слово может содержать точки ., где точки могут быть соответствует любой букве.
Моя стратегия:
Моя стратегия предполагает представление дерева с помощью хэш-карты вместо традиционной древовидной структуры на основе связанных списков, стремясь к повышению производительности и снижению сложности. Используя хэш-карту, мы можем быстро получить доступ к следующему узлу, не проходя через ненужные узлы, что ускоряет операции, особенно с большими наборами данных.
Например, при вставке в эту структуру таких слов, как «яблоко» и «приложение», она организуется как вложенные хэш-карты, где каждый символ в слове указывает на другую хэш-карту, представляющую следующий символ. Конец слова отмечается специальной парой ключ-значение {'end': {}}. Таким образом, мы эффективно сохраняем и ищем слова с минимальной пространственной и временной сложностью.
Мой код:
класс WordDictionary(объект): защита __init__(сам): self.map = {} Защиту addWord(я, слово): """ :введите слово: ул :rtype: Нет """ текущий = self.map для меня в слове: если я в текущем: ток = ток[я] еще: текущий [я] = {} ток = ток[я] текущий['конец'] = {} возвращаться def search(сам, слово): """ :введите слово: ул :rtype: бул """ текущий = self.map для меня в слове: если я в текущем: ток = ток[я] элиф я == '.': текущий = {ключ: значение для d в current.values() для ключа, значение в d.items()} еще: вернуть ложь если «конец» в текущем: вернуть истину вернуть ложь Решение кажется эффективным в большинстве случаев, но я столкнулся с ошибкой в тестовом примере 16, который не дает правильного результата. Из-за длины тестового примера 16 особенно сложно определить, где происходит ошибка. Мне нужны советы, как найти и исправить эту логическую ошибку. Сможете ли вы помочь во всем разобраться?
