leetcode 438:Find All Anagrams in a String 找变位子串

Find All Anagrams in a String 找变位子串:

本题难度为easy  当看到题目的第一眼 有些怀疑  怎么能等级那么简单  通过网上找到思路后发现 确实不难  现整理总结思路

原字符串s,在s中寻找字符串p的变位字符串的位置,并依次输出,且字符串元素均为小写字母。

思路:首先题目中给定 只有小写字母 所以可以用一个数组长度26来包含完所有的元素情况 并记录其对应出现次数 当然首先应该记录的应该是p的元素的对应次数pvec

然后再s中,从第一个元素开始往后找 在长度一样时 每次与pvec来比较 与p的元素和所对应的次数是否完全一样 在这个过程中 与顺序无关  且当s中元素往后移动一位 

前面起始位置都应该后移一位

过程:

1、记录p中元素及其出现次数 :pvec

2、在s中 从位置0开始依次后移 依次往后记录当前s中元素出现的次数svec

3、在当前s记录过程中 长度达到p的长度时  就要从开始端移除最开始元素了

4、比较svec中元素记录和pvec中是否相等 相等则表示在这一长度中 找到了p的一个变位子串位置 即为s中当前长度的开始位置 并记录下来

5、转第二步 直至s中元素记录完毕

 

代码:

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

     

原文地址:https://www.cnblogs.com/weiyi-mgh/p/6291159.html