tgoop.com/csharpproglib/6351
Create:
Last Update:
Last Update:
Задача: дана строка s и строка p. Необходимо найти все начальные индексы подстрок в s, которые являются анаграммами строки p.
Анаграмма — это слово или фраза, образованная перестановкой букв другого слова, используя все исходные буквы ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Объяснение:
Подстрока с индекса 0 - "cba", анаграмма "abc".
Подстрока с индекса 6 - "bac", анаграмма "abc".
Оптимальное решение использует технику скользящего окна с подсчетом частот символов.
1. Подсчитываем количество и частоту всех символов в строке p
2. Создаем скользящее окно размером со строку
p в строке s3. Для каждой позиции окна сравниваем частоты символов с эталоном
4. При совпадении добавляем индекс в результат
Код:
public class Solution
{
public IList<int> FindAnagrams(string s, string p)
{
List<int> result = new List<int>();
if (s.Length < p.Length)
return result;
// Массивы для подсчета частот символов (26 букв английского алфавита)
int[] pCount = new int[26];
int[] windowCount = new int[26];
// Подсчитываем частоты в строке p и первом окне
for (int i = 0; i < p.Length; i++)
{
pCount[p[i] - 'a']++;
windowCount[s[i] - 'a']++;
}
// Проверяем первое окно
if (AreEqual(pCount, windowCount))
result.Add(0);
// Скользим окном по строке s
for (int i = p.Length; i < s.Length; i++)
{
// Добавляем новый символ справа
windowCount[s[i] - 'a']++;
// Удаляем старый символ слева
windowCount[s[i - p.Length] - 'a']--;
// Проверяем текущее окно
if (AreEqual(pCount, windowCount))
result.Add(i - p.Length + 1);
}
return result;
}
// Вспомогательный метод для сравнения массивов частот
private bool AreEqual(int[] arr1, int[] arr2)
{
for (int i = 0; i < 26; i++)
{
if (arr1[i] != arr2[i])
return false;
}
return true;
}
}
#dotnet_challenge