Задача 438 «Найти все анаграммы в строке» — это распространенная задача кодирования, которую можно решить с помощью метода скользящего окна и подсчета частот. Цель — найти все начальные индексы анаграмм более короткой строки (шаблона) внутри более длинной строки.
Вот пошаговое объяснение проблемы:
Постановка задачи: по двум строкам: s (более длинная строка) и p (более короткая строка) найти все начальные индексы анаграмм p в s.
Анаграмма — это слово или фраза, образованная путем перестановки букв другого слова, обычно с использованием всех исходных букв ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc" Output: [0, 6]
Пояснение: В данном примере «abc» — это более короткая строка (шаблон), которая образует анаграмму «cbaebabacd», начиная с индексов 0 и 6.
Подход: Чтобы эффективно решить эту проблему, вы можете использовать метод скользящего окна вместе с подсчетом частоты символов. Вот как работает этот подход:
- Создайте два массива,
pCount
иsCount
, оба размером 26, чтобы представить частоту каждого символа (от «a» до «z») в строке шаблонаp
и скользящем окне в строкеs
соответственно. Инициализируйте оба массива нулями. - Сначала заполните массив
pCount
частотами символов в строкеp
с помощью цикла. - Инициализируйте скользящее окно в
s
того же размера, что и шаблонp
. Заполните массивsCount
частотами символов в этом окне. - Продвигайте окно по строке
s
слева направо, обновляя массивsCount
по мере продвижения. На каждом шаге проверяйте, соответствует ли массивsCount
массивуpCount
. Если они совпадают, это означает, что найдена анаграммаp
, и вы записываете в результат начальный индекс анаграммы. - После каждого шага удаляйте самый левый символ из скользящего окна и добавляйте новый символ справа.
- Продолжайте этот процесс, пока скользящее окно не пройдет через всю строку
s
. - Наконец, верните список начальных индексов, в которых анаграммы
p
были найдены вs
.
/** * @param {string} s * @param {string} p * @return {number[]} */ var findAnagrams = function(s, p) { if (s.length < p.length) { return []; // If s is shorter than p, there can be no anagrams, so return an empty array. } const pCount = new Array(26).fill(0); // Array to store character frequency of string p (26 characters from 'a' to 'z'). const sCount = new Array(26).fill(0); // Array to store character frequency in the sliding window. const result = []; // Calculate character frequency of string p. for (let i = 0; i < p.length; i++) { // Get the Unicode code point of character p[i]. For example, if p[0] = 'a', the code point is 97. // Let's say. Calculate how far the current character is from 'a' by subtracting the code point of 'a'. // codePoint - 'a'.charCodeAt(0) = 97 - 97 = 0 // Thus, the current character 'a' is stored at index 0 in the array. pCount[p.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Initialize the sliding window. for (let i = 0; i < p.length; i++) { sCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Iterate through string s using a sliding window. for (let i = p.length; i < s.length; i++) { // Check if the character frequency in the current sliding window matches p. if (isEqual(pCount, sCount)) { result.push(i - p.length); } // Update the sliding window by removing the leftmost character and adding the new character. sCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; sCount[s.charCodeAt(i - p.length) - 'a'.charCodeAt(0)]--; } // Check one more time after the loop ends. if (isEqual(pCount, sCount)) { result.push(s.length - p.length); } return result; }; // Function to check if two character frequency arrays are equal. function isEqual(arr1, arr2) { for (let i = 0; i < 26; i++) { if (arr1[i] !== arr2[i]) { return false; } } return true; } console.log(findAnagrams("cbaebabacd", "abc")); // Output: [0, 6]
Анализ сложности:
- Временная сложность: O(N), где N — длина строки
s
. Это связано с тем, что мы проходим всю строку один раз с помощью скользящего окна. - Пространственная сложность: O(1), так как размер массивов
pCount
иsCount
постоянен (26), а остальное использование пространства минимально.
Этот подход эффективно находит все начальные индексы анаграмм шаблона p
внутри строки s
без необходимости использования вложенных циклов или лишнего пространства.
Похожие проблемы:
3. Самая длинная подстрока без повторяющихся символов
76. Минимальная подстрока окна
239. Максимум скользящего окна
424. Замена самого длинного повторяющегося символа
567. Перестановка в строке