438. Find All Anagrams in a String
Hash Table, String, Sliding Window, Review, AMateList ·Problem Statement
link: LeetCode.cn LeetCode
Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Input: s = "abab", p = "ab"
Output: [0,1,2]
Solution Approach
The key idea of the solution is to utilize a sliding window approach while maintaining character frequency counts to efficiently find all anagrams of string p within string s.
Algorithm
-
Frequency Computation: Calculate character frequencies in p.
-
Sliding Window: Slide a window of size len(p) over s, updating character frequencies dynamically.
-
Comparison: Check if the frequency counts of characters in the window match those of p, indicating an anagram, and record the starting index of the window.
Implement
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
def f(c):
return ord(c) - 97
if len(p) > len(s):
return []
ct_s, ct_p = [0] * 26, [0] * 26
l = len(p)
res = []
for ch in p:
c = f(ch)
ct_p[c] += 1
for i in range(l - 1):
ct_s[f(s[i])] += 1
for i, c in enumerate(s[l - 1:]):
ct_s[f(c)] += 1
if ct_s == ct_p:
res.append(i)
ct_s[f(s[i])] -= 1
return res