LeetCode - 567 解題紀錄

題目： LeetCode - 567. Permutation in String

題目說明

給兩個 String s1、s2，求 s2 中是否有某段文字結構組成和 s1 相同。

解題思路

建兩個表，v1 放 s1 中的英文字母個數，v2 放 s2 某段的英文字母個數。使用一個迴圈遍歷 s2，將遍歷到的元素加入 v2，當裡面存放的字母個數超過 s2 的長度時，需要把最前面的刪除。最後判斷 v2 是否等於 v1 即可。

參考解法

// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int l1 = s1.size(), l2 = s2.size();
        vector<int> v1(26), v2(26);
        for(auto c : s1)
            ++v1[c - 'a'];
        for(int i = 0; i < l2; ++i)
        {
            if(i >= l1)
                --v2[s2[i - l1] - 'a'];
            ++v2[s2[i] - 'a'];
            if(v1 == v2)
                return true;
        }
        return false;
    }
};