32-й день карантина: может быть, мне стоит постараться быть продуктивным?

В рамках своего решения «новый карантинный месяц, новый я» я прибегнул к решению большего количества задач на Leetcode, чтобы укрепить свои навыки решения проблем, а также дать моему мозгу хорошую тренировку. Потому что в последнее время у него возникли проблемы с вычислением 2+2 (ответ — яблоки, верно?). Поэтому я решил продолжить свое старое увлечение решением задач Leetcode.

Сегодняшняя задача — сделать Trie (https://leetcode.com/problems/implement-trie-prefix-tree/).

Я надел шапку для размышлений, включил Linkin Park и включил. Моим первым побуждением было использовать карту. Потому что это было бы

A) Экономия времени: с тех пор, как я узнал, что среднее время поиска карты составляет O (1), я влюбился в нее.

B) Экономия места: поскольку моей другой идеей было использование 2D-списка/массива, что привело бы к множеству пустых «дыр» для будущих алфавитов, которых в настоящее время нет в дереве.

Ладно, решил воспользоваться картой. Что теперь? Как концептуализировать попытку как карту? Я подумал о реализации Linked List-y, где вместо

Узел-›Узел|Значение

Я бы сделал что-то вроде

Ключ

Алфавит-> Карта Алфавитов (Так что эта карта имеет только буквы, с которыми «связан» Ключ. То есть, если я введу эй, карта будет

h -> Карта только с ключом e -> Карта только с ключом y -> пусто

Но я все еще не мог уложить это в голове, мой мозг отказывался сотрудничать. Я решил приготовить ужин. Пельмени, ням, вкусные. Эврика! У меня может быть своя реализация, давайте попробуем.

Я остановился на реализации Map‹Character, Trie›, где каждое значение было бы Trie само по себе. Итак, гибрид древовидного списка (вроде). Теперь нужно проверить, будут ли мои методы (вставка, поиск, запуск) совместимы с моей реализацией.

Вставить было легко, я использовал метод вставки, подобный связанному списку, используя временную переменную Trie, чтобы пройти через существующий Trie и вставить слово.

Сложность: линейна по длине слова.

Оглядываясь назад: я не нашел способа пометить, закончилось ли слово, что очень скоро вернется, чтобы преследовать меня.

Поэтому, не оглядываясь назад, я начал думать о вставке и запуске с. Я пришел к, казалось бы, простому, но эффективному решению, что search и startwith являются противоположностями друг друга (Спойлер: это не так). Поэтому я написал метод, который, по сути, брал слово, проходил через дерево, если оно достигало конца слова, а «Значение» текущего ключа было пустым, это означало, что оно присутствует на карте, но не соответствует требованиям. для «начинается с», так как из него нет букв, которые составляют другое слово.

Если вы так же умны, как я, то вы также заметите очень очевидный недостаток в плане.

Вставить("каран")

Поиск («каран»). Истинный. Ожидаемое поведение

Начинается с («каран»). Ложь. Опять же, ожидаемое поведение. Вот где это становится весело.

Вставить ("ка").

Поиск («ка»). Ложь. Мне грустно :(

Так как моя реализация не помечала «ка» как слово, оно не отображалось в моем методе поиска как таковое.

Я исправил это? Да, да, я сделал.

Я боролся с несколькими решениями.

Используйте логическое значение, чтобы отслеживать конец слова. Проблема? Куда бы я вставил логическое значение? Невозможно вставить логическое значение в символ, попробуйте ввести карту.

В порядке. Не логическое значение, как насчет использования чего-то вроде логического значения? Вот тогда у меня был еще один момент Эврики, и я решил добавить ко всем вставкам «.»! Простая точка, чтобы отметить конец слова.

Как оказалось, это было решением!

Наконец выбил это из парка, это было принято!

Итак, в конце концов

Хорошо: было принято

Плохо. Это было быстрее, чем всего 12,7 % всех решений Java, что означает, что есть много возможностей для улучшения.

Области улучшения. По моему мнению, если бы я поработал над этим немного больше, я мог бы найти способ использовать поиск и startwith в тандеме, чтобы было немного больше повторного использования кода.

Кроме того, я ищу идеи о том, как я мог бы сделать некоторые оптимизации, чтобы это было быстрее. Я сейчас ни о чем не могу думать, но, может быть, это потому, что сейчас 1:12 ночи, и мне определенно пора спать.

В любом случае, до завтрашней увлекательной сессии!

Реализацию можно найти по адресу: https://github.com/karankaushik95/LeetCode-Medium/blob/master/TrieSolution.java