Як вирішити проблему кодування Шерлока та Анаграм у JavaScript

Ця публікація допоможе вам розв’язати моє рішення завдання кодування під назвою „Шерлок і анаграми”. Ви можете поглянути на це в HackerRank.

Я витратив багато часу, намагаючись вирішити це за допомогою JavaScript. Коли я спробував загуглити, я не зміг знайти гідне рішення JS. Я знайшов лише один, і він працював неправильно. Крім того, про будь-які пояснення не могло бути й мови. Ось чому я вирішив написати про це статтю і спробувати запропонувати кілька приємних та легкозасвоюваних пояснень. Продовжуйте читати зараз!

⚠️ПОПЕРЕДЖЕННЯ: Я викладу своє рішення нижче з короткими поясненнями щодо кожного з кроків. Якщо ви хочете спробувати самостійно, будь ласка, зупиніться тут і перейдіть на сайт HackerRank.

Проблема

Два рядки є анаграмами один одного, якщо букви одного рядка можна переставити так, щоб утворити інший рядок. Враховуючи рядок, знайдіть кількість пар підрядків рядка, які є анаграмами один одного.

Наприклад s = mom , список усіх анаграмматичних пар дорівнює [ m, m ], [ mo, om ] у положеннях [[0], [2]], [[0, 1], [1, 2]] відповідно .

Обмеження

Довжина вхідного рядка: 2 ≤ | s | ≤ 100

Рядок s містить лише малі літери з діапазону ascii [az].

Аналіз

Перш за все - нам потрібно краще зрозуміти всю проблему. Що таке анаграма? Що таке анаграмматична пара? Чи можу я побачити один? Крім того, що саме це означає підрядки ?

Іншими словами, нам потрібно мати чітке уявлення про те, що ми намагаємось вирішити, перш ніж це вирішити.

З опису проблеми ми можемо вирахувати все, що нам потрібно. Продовжуй йти! ?

Я вважаю, що зараз сприятливий момент згадати, що проблема, про яку йдеться, знаходиться в розділі «Словники та хеш-карти» на веб-сайті HackerRank. Ви, мабуть, подумаєте, що вам слід використовувати такий тип даних при її вирішенні. ?

Анаграми

Оскільки ми будемо шукати анаграми, почнемо з них. Як описано вище, анаграма одного слова - це інше слово, яке має однакову довжину і створюється з однаковими символами попереднього слова.

Тож нам доведеться шукати слова та порівнювати їх з іншими словами, щоб перевірити, чи це анаграмматичні пари. Після знаходження ми просто підрахуємо їх.

Анаграмматичні пари

Оскільки ми побачили, що таке анаграма, слід порівняно легко зробити висновок, що анаграмматична пара - це лише два рядки, які є анаграмами. Такі як "мо" та "ом", або "слухати" та "мовчати". Нам доведеться підрахувати, скільки таких пар можна знайти у даному рядку. Для цього нам потрібно розділити цей оригінальний рядок на підрядки.

Підрядки

Підрядки, як випливає з назви, є частинами рядка. Ці частини можуть бути просто літерою або парою букв, наприклад, що ми бачили у прикладі вище - " m " або " mo. ”У нашому рішенні ми розділимо вихідний рядок на такі підрядки, а потім переглянемо їх і проведемо порівняння, яке покаже нам, чи є серед них анаграмматичні пари.

Рішення

Тепер, коли ми зробили аналіз, настав час показу! ?

Підсумуємо:

  1. Нам потрібно знайти всі підрядки даного рядка - створіть для цього метод.
  2. Нам потрібно мати можливість перевірити, чи два рядки є анаграмами - створіть для цього метод.
  3. Нам потрібно порахувати всі анаграмматичні пари в даному рядку - створіть для цього метод.
  4. Об'єднайте все зверху і плюньте результат - створіть для цього метод.

Отримати всі підрядки

Це буде нашим допоміжним методом для пошуку всіх підрядків даного рядка:

function getAllSubstrings(str) { let i, j, result = []; for (i = 0; i < str.length; i++) { for (j = i + 1; j < str.length + 1; j++) { result.push(str.slice(i, j)) } } return result }

Як бачите, він має складність часу O (n²). У нашому випадку це робить свою роботу, оскільки ми маємо обмежену довжину вхідного рядка (до 100 символів).

Перевірте наявність анаграм

Це буде наш допоміжний метод для перевірки, чи є два рядки анаграмматичними парами:

function isAnagram(str1, str2) { const hist = {} for (let i = 0; i < str1.length; i++) { const char = str1[i] if (hist[char]) { hist[char]++ } else { hist[char] = 1 } } for (let j = 0; j < str2.length; j++) { const char = str2[j] if (hist[char]) { hist[char]-- } else { return false } } return true }

Пам'ятайте, що ми припускали, що, швидше за все, нам доведеться використовувати такі структури даних, як хеш-карти або словники (враховуючи розділ, де цей виклик міститься на HackerRank).

Ми використовуємо простий об’єкт JavaScript, щоб грати роль хеш-карти. Ми робимо дві ітерації - по одній на рядок. Коли ми робимо ітерацію над першим, ми додаємо його символи як ключі до хеш-карти та підраховуємо їх появу, яка буде зберігатися як їх значення. Потім ми робимо ще одну ітерацію над другим рядком. Перевірте, чи зберігаються його символи в нашій хеш-капі. Якщо так - зменшіть їх вартість. Якщо відсутні символи, це означає, що ці два рядки не є анаграмматичною парою, ми просто повертаємо false. Якщо обидва цикли завершені, ми повертаємо true, що означає, що аналізовані рядки є анаграмматичною парою.

Зробіть підрахунок

Це метод, за допомогою якого ми будемо використовувати помічник для перевірки того, чи є пара анаграмматичним, і підраховувати її. Ми робимо це за допомогою масивів JavaScript та методів, які вони надають. Ми перебираємо масив, що містить усі підрядки вихідного рядка. Тоді ми отримуємо правильний елемент і видаляємо його з масиву. А потім ми робимо ще один цикл через цей масив і повертаємо 1, якщо виявимо, що існує анаграма поточного елемента. Якщо нічого не знайдено, ми повертаємо 0.

function countAnagrams(currentIndex, arr) { const currentElement = arr[currentIndex] const arrRest = arr.slice(currentIndex + 1) let counter = 0 for (let i = 0; i < arrRest.length; i++) { if (currentElement.length === arrRest[i].length && isAnagram(currentElement, arrRest[i])) { counter++ } } return counter }

І зрештою

Єдине, що залишилося зробити зараз, - це поєднати все вищесказане і плюнути бажаний результат. Ось як виглядає остаточний метод:

function sherlockAndAnagrams(s) { const duplicatesCount = s.split('').filter((v, i) => s.indexOf(v) !== i).length if (!duplicatesCount) return 0 let anagramsCount = 0 const arr = getAllSubstrings(s) for (let i = 0; i < arr.length; i++) { anagramsCount += countAnagrams(i, arr) } return anagramsCount }

Можливо, ви помітили, тут я спочатку перевіряю наявність дублікатів, щоб знати, чи слід продовжувати далі. Як ніби немає дубльованих букв, тоді неможливо мати анаграму.

And finally, we get all substrings into an array, iterate over it, count the anagrammatic pairs that are found and return this number.

You can find the full code here.

Conclusion

These kind of exercises are very good for making you think algorithmically. Also they change your way of working in your day to day job. My recommendation would be to do the same I am trying to do — train your brain now and then with one of those. And if you can — share. I know sometimes you don’t have time for such challenges, but when you do — go for it.

My personal feeling after finishing this was total satisfaction, which is completely understandable, considering the time it took me to do it. But in the end, dear reader, I am even happier I can share this experience with you?!

Thanks for reading. Read more of my articles at mihail-gaberov.eu.