Недавно я решил задачу 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.

Я создаю это решение очень много. Если вы найдете другой подход или хотите оставить отзыв о моем решении, пожалуйста, сделайте это.

Спасибо за чтение!

Хорошего дня!