Problem: Given a string s and a non-empty pattern p, find all the start indices of p's anagrams in s.
Example:
Input: s: "abca" p: "abc" Output: [0, 1] Explanation: The substring with start index = 0 is "abc", which is an anagram of "abc". The substring with start index = 2 is "bca", which is an anagram of "abc".
Approach: We can use sliding window approach here. We can maintain a hash of pattern p with key as characters in p and value as frequencies of those characters. We also have to maintain the unique character counts to verify if actually an anagram is found or not.
Rest of the approach, you can understand by just looking at the code.
Implementation in C#:
public IList<int> FindAnagrams(string s, string p)
{
Dictionary<char, int> pCountDict = new Dictionary<char, int>();
foreach(char ch in p)
{
if (!pCountDict.ContainsKey(ch))
{
pCountDict.Add(ch, 0);
}
++pCountDict[ch];
}
int uniqueCharcount = pCountDict.Count;
int start = 0, end = 0;
List<int> result = new List<int>();
while (end < s.Length)
{
if (pCountDict.ContainsKey(s[end]))
{
--pCountDict[s[end]];
if (pCountDict[s[end]] == 0)
{
--uniqueCharcount;
}
}
if (end - start + 1 == p.Length)
{
if (uniqueCharcount == 0)
{
result.Add(start);
}
if (pCountDict.ContainsKey(s[start]))
{
++pCountDict[s[start]];
if (pCountDict[s[start]] == 1)
{
++uniqueCharcount;
}
}
++start;
}
++end;
}
return result;
}
Another Implementation:
public IList<int> FindAnagrams1(string s, string p)
{
if (s?.Length < p?.Length)
{
return new List<int>();
}
int[] pCount = new int[26];
int[] sCount = new int[26];
for (int i = 0; i < p.Length; ++i)
{
++pCount[p[i] - 'a'];
++sCount[s[i] - 'a'];
}
var result = new List<int>();
if (pCount.SequenceEqual(sCount))
{
result.Add(0);
}
int start = 0;
for (int i = p.Length; i < s.Length; ++i)
{
--sCount[s[start++] - 'a'];
++sCount[s[i] - 'a'];
if (pCount.SequenceEqual(sCount))
{
result.Add(start);
}
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment