438. Найти все анаграммы в строке (Find All Anagrams in a String)

Задание.

Получены две строки s и p.

Возвратите массив всех начальных индексов, для которых в строке ‘s’ содержится анаграмма для p. ответ можно вернуть в любом порядке.

Анаграмма – это слово или фраза, образованные путем перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример 1.

Входные данные: s = “cbaebabacd”, p = “abc”

Результат: [0,6]

Объяснение:

Подстрока со стартовым индексом = 0 – это “cba”, что является анаграммой “abc”.

Подстрока со стартовым индексом = 6 – это “bac”, что является анаграммой “abc”.

Пример 2.

Входные данные: s = “abab”, p = “ab”

Результат: [0,1,2]

Объяснение:

Подстрока со стартовым индексом = 0 – это “ab”, что является анаграммой “ab”.

Подстрока со стартовым индексом = 1 – это “ba”, что является анаграммой “ab”.

Подстрока со стартовым индексом = 2 – это “ab”, что является анаграммой “ab”.

Решение.

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> pvec(26, 0), svec(26, 0), res;
        if(p.size()>s.size())
            return res;
        for(int i=0;i<p.size();i++) {
            pvec[p[i]-'a']++;
            svec[s[i]-'a']++;
        }
        if(pvec==svec)
            res.push_back(0);
        int k=p.size();
        for(int i=p.size();i<s.size();i++) {
            svec[s[i-k]-'a']-=1;
            svec[s[i]-'a']+=1;
            if(svec==pvec)
                res.push_back(i-k+1);
        }
        return res;
    }
};

Способ решения.