Попробуй, попробуй, попробуй еще раз!

Аудитория

Эта статья предназначена для разработчиков, имеющих практический опыт работы с деревьями (покопаться в моей статье можно здесь). В нем дается краткий обзор попыток и их применения, а в заключение приводится работающий пример задачи, ориентированной на попытки.

Аргумент

Попытки — это тип древовидной структуры данных, он содержит узлы, ребра, корень и отношения родитель-потомок. Тем не менее, trie действует как хранилище данных "ключ-значение". Ключ всегда является строкой, но значение может быть любым. На самом деле, ценность может быть вообще никакой! Попытки также можно использовать для хранения уникального списка ключей.

Давайте рассмотрим эту концепцию на примере.

На приведенной выше диаграмме у нас есть попытка хранения словарей фамилий в именах. Мы видим, что он содержит одну фамилию (Смит) и одно имя (Джон). Давайте добавим еще двух человек, Джейн Смит и Агона Смакая.

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

Одно из распространенных применений этого шаблона — первичные ключи в хранилищах данных. Кроме того, мы можем использовать его для поиска значений по префиксу. Если бы мы искали имена людей, фамилия которых начинается с «Sm», мы могли бы использовать эту структуру для получения всех трех наших записей. Часто по мере расширения попыток мы будем ограничивать эти выборки заданным числом, скажем, первым m.

Гибридные попытки

Из предыдущих диаграмм мы можем заметить, что эта структура наиболее полезна, когда наши ключи имеют много общих букв. Если это не так, то наше дерево становится слишком раскидистым и перестает быть полезным.

Чтобы обойти эту проблему, мы можем использовать гибридную структуру.

Мы устанавливаем порог для нашего дерева и продолжаем добавлять строки к узлу, пока не достигнем этого порога. На этом этапе мы расширяем узел до более традиционной древовидной структуры и продолжаем, как раньше.

Использование попыток

Эта задача взята из LeetCode и формулируется следующим образом.

В английском языке у нас есть понятие корень, за которым может следовать какое-то другое слово, образуя другое более длинное слово — назовем это слово преемником. Например, если за коренью "an" следует последующее слово "other", мы можем сформировать новое слово "another".

Учитывая dictionary, состоящее из многих корней, и sentence, состоящее из слов, разделенных пробелами, замените все преемники в предложении на корень, образующий его. . Если преемник может быть заменен более чем одним корнем, замените его корнем с наименьшей длиной. .

Верните sentence после замены.

Представьте, что нам предоставлен словарь слов: летучая мышь, кошка и крыса. Мы можем расширить это в три ниже (простите за двойное использование root).

Чтобы найти кратчайший корень преемника, мы спускаемся вниз по дереву, сопоставляя буквы, пока не достигнем конца ветви. Это наш корень. Если нет совпадения для начальной буквы, то не существует корня (например, жир не будет соответствовать чему-либо).

У нас есть решение ниже

Вывод

В заключение мы рассмотрели попытки, их свойства и привели рабочий пример.