Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. Strings consists of lowercase English letters only.
Example 1:
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".
Example 2:
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Solution: (Pattern matching but direct algorithms cannot be used)
Algorithm:
The idea is to use two count arrays:
1) The first count array store frequencies of characters in pattern.
2) The second count array stores frequencies of characters in current window of text.
class Solution
{
public:
bool compare(vector<int> &pat, vector<int> &str)
{
for (int i = 0; i <= 25; i++)
{
if (pat[i] != str[i])
{
return false;
}
}
return true;
}
vector<int> findAnaTime Complexity: O(n)grams(string s, string p)
{
vector<int> v;
if (s == "" || p.length() > s.length())
{
return v;
}
// Arrays to maintain count of characters
vector<int> pat(26);
vector<int> str(26);
for (int i = 0; i < p.length(); i++)
{
pat[p[i] - 97]++;
str[s[i] - 97]++;
}
int l = p.length();
for (int i = 0; i <= s.length() - l; i++)
{
//comparing two arrays
if (compare(pat, str))
{
v.push_back(i);
}
// Removing prev char count
str[s[i] - 97]--;
// Increasing next char count
if (i + l < s.length())
{
str[s[i + l] - 97]++;
}
}
return v;
}
};