🎯 Готовы ли вы решить классическую проблему LeetCode и погрузиться в мир обнаружения анаграмм? Присоединяйтесь к нам, пока мы изучаем увлекательный алгоритм для определения анаграмм в строках и оттачиваем свои навыки программирования! 📝

Сообщение в блоге углубляется в код решения, предлагая подробные объяснения для каждого компонента и шага. Он включает пример пробного прогона, что позволяет начинающим программистам легко визуализировать процесс.

Постановка задачи

Имея две строки, s и p, ваша задача состоит в том, чтобы найти все начальные индексы анаграмм p в пределах s. Проще говоря, вы пытаетесь обнаружить позиции, в которых буквы p могут быть переставлены так, чтобы образовать подстроку s. Давайте погрузимся в решение шаг за шагом, чтобы разгадать тайну! 💡

Пример проблемы 📋

  • Ввод: s = "cbaebabacd", p = "abc"
  • Вывод: [0, 6]
  • Объяснение. Подстроки, начинающиеся с индекса 0 ("cba") и индекса 6 ("bac"), являются анаграммами слова "abc".

Решение 🔧

Алгоритм обнаружения анаграмм

Вот дорожная карта, чтобы раскрыть скрытые анаграммы в строках:

  1. Создание карты частот: начните с создания карты частот для символов строки p. Эта карта будет вашим путеводителем по отслеживанию появления персонажей.
  2. Использование скользящего окна: используйте технику скользящего окна для перемещения по строке s. Начните с окна того же размера, что и длина p.
  3. Начальная проверка окна: в открывающемся окне уменьшите частоту символов, присутствующих в s. Если карта частот достигает всех нулей, потенциальная анаграмма возникает из индекса 0.
  4. Shift and Slide: перемещение окна на один шаг за раз. Настройте карту частот, когда вы удаляете начальный символ и вводите конечный символ окна.
  5. Проверка анаграмм: на каждом шаге проверяйте, содержит ли карта частот снова все нули. Если это так, вы обнаружили анаграмму в текущем индексе.
  6. Сбор трофеев: запишите индексы, в которых находятся анаграммы, и представьте результат в виде массива.

📝 Код:

/**
 * @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