即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[LeetCode]438. Find All Anagrams in a String

编程语言 Lcharon 14℃ 0评论
本文目录
[隐藏]

1.[LeetCode]438. Find All Anagrams in a String

1.1.题目描述

这里写图片描述

1.2.思路

暴力匹配会超时


使用滑窗做,首先计算p对应的pArr


然后滑窗计算s对应的sArr,窗口大小为p的长度

1.3.代码

#include 
#include 
#include 

using namespace std;

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

            }
            else {
                sArr[s[i - 1] - 'a'] --;
                sArr[s[i + len - 1] - 'a'] ++;
            }

            if (sArr == pArr)
                res.push_back(i);
        }
        return res;
    }
};

int main() {
    Solution s;
    vector<int> res = s.findAnagrams("abab", "ab");
    for(int p : res)
        cout << p << " ";

    cout << endl;

    system("pause");
    return 0;
}

转载请注明:CodingBlog » [LeetCode]438. Find All Anagrams in a String

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情