Недавно я решил задачу HackerRank под названием Tries: Contacts без использования структуры данных trys. Ссылку на этот блог можно найти здесь. Узнав, что такое структура данных trys, я изменил свое решение, чтобы использовать его.
Суть проблемы
Создайте алгоритм для добавления контактов и сможете найти количество предложений даже при частичном вводе.
add david //adds david to your contacts add danelle //adds danelle to your contacts find da //prints 2 as the two contacts we have stored start with "da"
Что такое структура данных trie?
Структура данных trie используется для хранения динамического набора или ассоциативного массива, где ключи вложены друг в друга и имеют указатели.
Решение
Мне очень понравилось делать это решение, и я расскажу о нем дальше в блоге.
function check(input){ //remove number of commands input.shift() //create store of possible searches let store = {} input.forEach(command => { let splitCommand = command.split(" ") let contact = splitCommand[1] let instruction = splitCommand[0] //3 means add and 4 means find //ref to store let ref = store let letters = contact.split("") if(instruction == "add"){ //ADD for(var i = 0; i < letters.length; i++){ if(ref[letters[i]]){ ref[letters[i]]["counter"]++ }else{ ref[letters[i]] = {"counter": 1} } //change the value of ref ref = ref[letters[i]] } }else if(instruction == "find"){ //FIND for(var i = 0; i < letters.length; i++){ ref = ref[letters[i]] if(!ref){ break } } ref ? console.log(ref["counter"]) : console.log(0) } }) }
Разобьем эту проблему на части.
Разбивка
Мы будем тестировать с этим вводом.
[3, "add david", "add danelle", "find da"]
Шаг 1
Обратите внимание, что первый ввод — это общее количество команд в массиве. Мне это не нужно, поэтому я удаляю первый элемент массива с помощью «input.shift()».
["add david", "add danelle", "find da"]
Шаг 2
Теперь, когда наш массив очищен и содержит только команды. Мы можем создать наш магазин.
let store = {}
Шаг 3
Давайте пройдемся по списку команд и разделим каждую команду на части. Мы также создадим ссылку на наш магазин под названием «ref». Подробнее о «ref» чуть позже. Хотя в этом нет необходимости, мы также создали две переменные, называемые контактом и инструкцией, чтобы сделать намерение более читабельным. Наконец, нам нужно разделить наш контакт на отдельные письма.
input.forEach(command => { let splitCommand = command.split(" ") let contact = splitCommand[1] let instruction = splitCommand[0] //3 means add and 4 means find //ref to store let ref = store let letters = contact.split("") }
Шаг 4
Нам нужны условные выражения для нашей инструкции, чтобы определить, что нам нужно делать дальше.
if(instruction == "add"){ //ADD }else if(instruction == "find"){ //FIND }
Шаг 5. ДОБАВИТЬ
Теперь нам нужно добавить наши письма в наш магазин в соответствующем вложенном порядке и отслеживать, сколько писем мы встретили.
//ADD for(var i = 0; i < letters.length; i++){ if(ref[letters[i]]){ ref[letters[i]]["counter"]++ }else{ ref[letters[i]] = {"counter": 1} } //change the value of ref ref = ref[letters[i]] }
Я хочу, чтобы мы немного разобрали это, потому что именно здесь происходит половина волшебства. Когда мы повторяем каждую букву.
["d", "a", "v", "i", "d"]
Если в хранилище нет ключа, мы создаем объект, у которого есть ключ «счетчик» со значением 1, установив его с помощью «ref». После установки мы устанавливаем «ref» на этот ключ в объекте. Если в хранилище есть ключ, мы увеличиваем счетчик, используя «ref» таким же образом. «ref» является динамическим и всегда указывает на следующий в нашем вложенном объекте.
Наш магазин должен выглядеть так, если добавить «da» из «david».
{"d": "counter": 1, "a": {"counter": "1"}}
Шаг 6 НАЙТИ
Наша находка работает очень похоже на нашу надстройку.
//FIND for(var i = 0; i < letters.length; i++){ ref = ref[letters[i]] if(!ref){ break } }
Мы перебираем наш магазин, используя «ref». Если мы найдем букву, то мы присвоим ее ссылку «ref», и если продолжить присвоение, значение выйдет из цикла, используя break.
Шаг 7
ref ? console.log(ref["counter"]) : console.log(0)
Если у ref есть have, мы печатаем значение его ключевого «счетчика», иначе мы печатаем 0.
Я создаю это решение очень много. Если вы найдете другой подход или хотите оставить отзыв о моем решении, пожалуйста, сделайте это.
Спасибо за чтение!
Хорошего дня!