Сложность: medium
Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
👨💻 Алгоритм:
1⃣Построить эталонный счетчик pCount для строки p.
2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.
3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.
😎 Решение:
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
if ns < np:
return []
pCount = Counter(p)
sCount = Counter()
output = []
for i in range(ns):
sCount[s[i]] += 1
if i >= np:
if sCount[s[i - np]] == 1:
del sCount[s[i - np]]
else:
sCount[s[i - np]] -= 1
if pCount == sCount:
output.append(i - np + 1)
return output
Ставь 👍 и забирай 📚 Базу знаний