Как да решим предизвикателството за кодиране на Sherlock и Anagrams в JavaScript

Снимка на Хавиер Кесада на Unsplash

Първоначално публикуван на mihail-gaberov.eu.

Тази публикация ще ви преведе през моето решение на кодиращо предизвикателство, наречено „Шерлок и анаграми.“ Може да го разгледате в HackerRank.

Прекарах много време в опит да го реша с JavaScript. Когато се опитах да го google, не можах да намеря прилично JS решение. Намерих само едно и не работи коректно. Също така, всякакви обяснения бяха напълно безспорни. Ето защо реших да напиша статия за това и се опитах да добавя някои хубави и лесни за смилане обяснения по пътя. Продължете да четете сега!

ВНИМАНИЕ: Ще разкача решението си по-долу с кратки обяснения за всяка от стъпките. Ако искате да опитате сами, моля, спрете тук и отидете на сайта на HackerRank.

проблем

Два низа са анаграми една на друга, ако буквите на един низ могат да бъдат пренаредени, за да образуват другия низ. Като се даде низ, намерете броя на двойките подтези на низ, които са анаграми един на друг.

Например s = mom, списъкът на всички анаграматични двойки е [m, m], [mo, om] на позиции [[0], [2]], [[0, 1], [1, 2]] съответно ,

Ограничения
Дължина на входния низ: 2 ≤ | s | ≤ 100
String s съдържа само малки букви от диапазона ascii [a-z].

анализ

Първо нещо първо - трябва да разберем по-добре целия проблем. Какво е анаграма? Какво е анаграматична двойка? Мога ли да видя такъв? Също така, какво точно означава подредовете?

С други думи, трябва да имаме ясна картина на това, което се опитваме да решим, преди да го разрешим.

От описанието на проблема можем да извадим всичко необходимо. Продължавайте да ходите!

Мисля, че това е подходящ момент да споменем, че въпросното предизвикателство е в раздела „Речници и хешмапи“ в уебсайта на HackerRank. Вероятно ще си помислите, че трябва да използвате този вид структура от данни, когато го решавате.

анаграми

Тъй като ще търсим анаграми, нека започнем с тях. Както е описано по-горе, анаграма на една дума е друга дума, която има същата дължина и е създадена със същите знаци от предишната дума.

Анимация за анаграмата „Слушай = мълчи“

Така че ще трябва да търсим думи и да ги сравняваме с други думи, за да видим дали са анаграматични двойки. След като бъдат намерени, просто ще ги преброим.

Анаграматични двойки

Тъй като видяхме какво представлява анаграма, трябва да бъде сравнително лесно да се заключи, че анаграматична двойка е само две струни, които са анаграми. Като „мо“ и „ом“, или „слушам“ и „безшумно“. Ще трябва да преброим колко двойки като тази могат да бъдат намерени в даден низ. За да направим това, трябва да разделим този първоначален низ на подстраници.

поднизове

Подредовете, както извежда името, са части от низ. Тези части могат да бъдат само буква или двойка букви, като това, което видяхме в примера по-горе - "m" или "mo". над тях и направете сравнението, което ще ни каже дали сред тях имаме анаграматични двойки.

Решение

Сега, когато направихме нашия анализ, е време за показване!

Нека обобщим:

  1. Трябва да намерим всички подредове от дадения низ - да създадем метод за това.
  2. Трябва да можем да проверим дали два низа са анаграми - създайте метод за това.
  3. Трябва да преброим всички анаграматични двойки в дадения низ - да създадем метод за това.
  4. Комбинирайте всичко отгоре и изплюйте резултата - създайте метод за това.

Вземете всички подтези

Това ще бъде нашият помощен метод за намиране на всички подтези от даден низ:

функция getAllSubstrings (str) {
  нека i, j, резултат = [];

  за (i = 0; i 

Както можете да видите, тя има O (n²) времева сложност. За нашия случай тя върши работа, защото имаме ограничена дължина на входния низ (до 100 знака).

Проверете за анаграми

Това ще бъде нашият помощен метод за проверка дали два низа са анаграматични двойки:

функция еAnagram (str1, str2) {
  const hist = {}

  за (нека i = 0; i 

Не забравяйте, че ние предположихме, че най-вероятно трябва да използваме структури от данни, като хеш-карти или речници (като се има предвид секцията, в която това предизвикателство се намира в HackerRank).

Използваме прост JavaScript обект, за да играем ролята на хешмап. Правим две повторения - по един на низ. Когато повтаряме първата, ние добавяме нейните символи като ключове към хешмапа и броим техните изяви, които ще бъдат запазени като техните стойности. След това правим още една итерация над втория низ. Проверете дали героите му се съхраняват в нашата хешмап. Ако да - намаляване на стойността им. Ако липсват знаци, което означава, че двата низа не са анаграматична двойка, ние просто връщаме невярно. Ако и двата цикъла са завършени, връщаме true, което означава, че низовете, които се анализират, са анаграматична двойка.

Направете броенето

Това е методът, при който ще използваме помощника за проверка дали дадена двойка е анаграматична и ще я преброим. Правим това с помощта на JavaScript масиви и методите, които предоставят. Итератираме над масив, съдържащ всички подтези на оригиналния низ. След това получаваме правилния елемент и го премахваме от масива. И тогава правим друг цикъл през този масив и връщаме 1, ако открием, че има анаграма на текущия елемент. Ако не се намери нищо, връщаме 0.

функция countAnagrams (currentIndex, arr) {
  const currentElement = arr [currentIndex]
  const arrRest = arr.slice (currentIndex + 1)
  нека брояч = 0

  за (нека i = 0; i 

И в крайна сметка

Единственото, което остава да се направи сега, е да комбинирате всичко по-горе и да изплюете желания резултат. Ето как изглежда крайният метод:

функция sherlockAndAnagrams (s) {
  const duplicatesCount = s.split (''). филтър ((v, i) => s.indexOf (v)! == i) .length

  ако (! duplicatesCount) върнете 0
  нека anagramsCount = 0

  const arr = getAllSubstrings (s)

  за (нека i = 0; i 

Може би сте забелязали, тук първо проверявам за дубликати, за да знам дали трябва да продължа по-нататък. Сякаш няма дублирани букви, тогава не е възможно да има анаграма.

И накрая, ние получаваме всички подредове в масив, итератираме над него, преброяваме анаграматичните двойки, които са намерени и връщаме това число.

Можете да намерите пълния код тук.

заключение

Този вид упражнения са много добри, за да ви накарат да мислите алгоритмично. Също така те променят начина ви на работа в ежедневната ви работа. Моята препоръка би била да направите същото, което се опитвам да правя - тренирайте мозъка си от време на време с едно от тях. И ако можете - споделете. Знам, че понякога нямате време за подобни предизвикателства, но когато го направите - продължете.

Личното ми чувство след приключването на това беше пълно удовлетворение, което е напълно разбираемо, като се има предвид времето, което ми отне да го направя. Но в крайна сметка, скъпи читателю, още по-щастлив съм, че мога да споделя това преживяване с вас!

Благодаря за четенето!