🎯 Готовы ли вы решить классическую проблему LeetCode и погрузиться в мир обнаружения анаграмм? Присоединяйтесь к нам, пока мы изучаем увлекательный алгоритм для определения анаграмм в строках и оттачиваем свои навыки программирования! 📝
Сообщение в блоге углубляется в код решения, предлагая подробные объяснения для каждого компонента и шага. Он включает пример пробного прогона, что позволяет начинающим программистам легко визуализировать процесс.
Постановка задачи
Имея две строки, s и p, ваша задача состоит в том, чтобы найти все начальные индексы анаграмм p в пределах s. Проще говоря, вы пытаетесь обнаружить позиции, в которых буквы p могут быть переставлены так, чтобы образовать подстроку s. Давайте погрузимся в решение шаг за шагом, чтобы разгадать тайну! 💡
Пример проблемы 📋
- Ввод: s = "cbaebabacd", p = "abc"
- Вывод: [0, 6]
- Объяснение. Подстроки, начинающиеся с индекса 0 ("cba") и индекса 6 ("bac"), являются анаграммами слова "abc".
Решение 🔧
Алгоритм обнаружения анаграмм
Вот дорожная карта, чтобы раскрыть скрытые анаграммы в строках:
- Создание карты частот: начните с создания карты частот для символов строки p. Эта карта будет вашим путеводителем по отслеживанию появления персонажей.
- Использование скользящего окна: используйте технику скользящего окна для перемещения по строке s. Начните с окна того же размера, что и длина p.
- Начальная проверка окна: в открывающемся окне уменьшите частоту символов, присутствующих в s. Если карта частот достигает всех нулей, потенциальная анаграмма возникает из индекса 0.
- Shift and Slide: перемещение окна на один шаг за раз. Настройте карту частот, когда вы удаляете начальный символ и вводите конечный символ окна.
- Проверка анаграмм: на каждом шаге проверяйте, содержит ли карта частот снова все нули. Если это так, вы обнаружили анаграмму в текущем индексе.
- Сбор трофеев: запишите индексы, в которых находятся анаграммы, и представьте результат в виде массива.
📝 Код:
/** * @param {string} s * @param {string} p * @return {number[]} */ var findAnagrams = function(s, p) { const pLen = p.length; const sLen = s.length; const pFreqMap = new Map(); const res = []; // Creating the map using p String for(let i=0;i<pLen;i++) { if(pFreqMap.has(p[i])) { pFreqMap.set(p[i], Number(pFreqMap.get(p[i]))+1); continue; } pFreqMap.set(p[i],1); } // Creating the first sliding window of pleN and finding if it's a anagram for(let i=0;i<pLen;i++) { if(pFreqMap.has(s[i])) { pFreqMap.set(s[i],pFreqMap.get(s[i])-1); } } // If it's a anagram - pushing the starting index for first Sliding window = 0 // We are checking if it's a anagram or not, by checking if the sliding window is all consumed or not if(allZeroInMap(pFreqMap)) res.push(0); // Creating the sliding window and moving it by one index everytime for(let i=1;i<sLen-pLen+1;i++) { // Discarding the last index, left behind the window if(pFreqMap.has(s[i-1])) { pFreqMap.set(s[i-1], pFreqMap.get(s[i-1])+1); } // Modyfying the map frequencing corresponding to the new index introduced in the window let k = i+pLen-1; if(pFreqMap.has(s[k])) { pFreqMap.set(s[k], pFreqMap.get(s[k])-1); } // Checking If it's a anagram - pushing the starting index for this Sliding window to res array if(allZeroInMap(pFreqMap)) res.push(i); } // returning the res array return res; }; const allZeroInMap = (nMap) => { for(const [key,value] of nMap) { if(value!==0) return false; } return true; }
Понимание кода на примере 🧐
Чтобы по-настоящему понять магию алгоритма, давайте рассмотрим пример. Рассмотрим s = «cbaebabacd» и p = «abc»:
- Изначально мы создаем карту частот для «abc».
- Мы начинаем сдвигать окно в s и проверяем, является ли каждое окно анаграммой «abc».
- По индексу 0 окно «cba» является анаграммой. Записываем индекс.
- Сдвигая окно, мы находим еще одну анаграмму «bac», начинающуюся с индекса 6.
Готовы отправиться в это путешествие по программированию? 🚀🔍 Прочтите другие решения от leetcode от The Rizz Coder здесь и улучшите свое мастерство программирования! Не пропустите — раскройте секреты задач по программированию вместе с нами.
#Решение проблем #CodingChallenges #AnagramDetection #LeetCodeSolutions #AlgorithmExploration #DataStructures
Ключевые слова SEO: LeetCode, Anagram ProblemCoding Challenge, Solution, Map Manipulation, Algorithmic Logic, Code Strategy, Solution Solutions, Beginner Coders, Coding Adventure, LeetCode Medium Problem