Написано: 23.03.2023

567. Перестановки в строке (Permutation in String)

medium

Задание.

Даны две строки s1 и s2

Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните значение true, если одна из перестановок s1 является подстрокой s2.

Пример 1.

Входные данные: s1 = “ab”, s2 = “eidbaooo”

Результат: true

Пояснение: s2 содержит одну перестановку s1 (“ba”).

Пример 2.

Входные данные: s1 = “ab”, s2 = “eidboaoo”

Результат: false

Решение.

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<int> s1vec(26, 0), s2vec(26, 0);
        if(m > n) {
            return false;
        }
        for(int i = 0; i < m; i++) {
            s1vec[ s1[i] - 'a']++;
            s2vec[ s2[i] - 'a']++;
        }
        if(s1vec == s2vec) {
            return true;
        }

        for(int i = m; i < n; i++) {
            s2vec[ s2[i-m] - 'a'] -= 1;
            s2vec[ s2[i] - 'a'] +=1;
            if(s1vec == s2vec) {
                return true;
            }
        }
        return false;
    }
};

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

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