🎯 Готови ли сте да се заемете с класически проблем с LeetCode и да се потопите в света на откриването на анаграми? Присъединете се към нас, докато изследваме завладяващ алгоритъм за идентифициране на анаграми в низове и изостряте уменията си за кодиране! 📝
Публикацията в блога се задълбочава в кода на решението, като предлага подробни обяснения за всеки компонент и стъпка. Той включва пример за сухо изпълнение, което улеснява начинаещите програмисти да визуализират процеса.
Постановка на проблема
Имайки два низа, s и p, вашата мисия е да намерите всички начални индекси на анаграмите на p в s. Казано по-просто, вие се стремите да откриете позициите, където буквите на p могат да бъдат пренаредени, за да образуват подниз от s. Нека се потопим в решението стъпка по стъпка, за да разгадаем мистерията! 💡
Пример за проблем 📋
- Вход: s = “cbaebabacd”, p = “abc”
- Изход: [0, 6]
- Обяснение: Поднизовете, започващи от индекс 0 („cba“) и индекс 6 („bac“), са анаграми на „abc“.
Решението 🔧
Алгоритъм за откриване на анаграма
Ето пътната карта за разкриване на скритите анаграми в низове:
- Създаване на честотна карта: Започнете с конструиране на честотна карта за знаците в низ p. Тази карта ще бъде вашето ръководство за проследяване на появявания на знаци.
- Прегръщане на плъзгащия се прозорец: Използвайте техниката на плъзгащия се прозорец, за да преминете през низ s. Започнете с прозорец със същия размер като дължината на p.
- Първоначална проверка на прозореца: В отварящия се прозорец намалете честотата на знаците, присъстващи в s. Ако честотната карта достигне всички нули, потенциална анаграма се появява от индекс 0.
- Shift и 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“ „тук“ и подобрете уменията си в кодирането! Не пропускайте – разкрийте тайните на предизвикателствата при кодирането с нас.
#ProblemSolving #CodingChallenges #AnagramDetection #LeetCodeSolutions #AlgorithmExploration #DataStructures
SEO ключови думи: LeetCode, Anagram ProblemCoding Challenge, Solution, Манипулиране на карти, Алгоритмична логика, Стратегия на кода, Решаване на проблеми, Начинаещи програмисти, Приключение с кодиране, LeetCode среден проблем