🎯 Готови ли сте да се заемете с класически проблем с 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 и 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“ „тук“ и подобрете уменията си в кодирането! Не пропускайте – разкрийте тайните на предизвикателствата при кодирането с нас.

#ProblemSolving #CodingChallenges #AnagramDetection #LeetCodeSolutions #AlgorithmExploration #DataStructures

SEO ключови думи: LeetCode, Anagram ProblemCoding Challenge, Solution, Манипулиране на карти, Алгоритмична логика, Стратегия на кода, Решаване на проблеми, Начинаещи програмисти, Приключение с кодиране, LeetCode среден проблем