欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Find All Anagrams in a String

程序员文章站 2022-03-21 21:21:55
...

Find All Anagrams in a String 

 1. 解析

题目大意,在字符串中查找给定的子序列,该子序列只要求出现的字符相同,而不要求顺序一样。

 2. 分析

整体上,这道题还是比较容易想到的。每次在s串中切割长度和p相同的字符串,然后比较它们出现的字符是否相同,如果一样,记录起点的位置;如果不一样,说明两个子串不相等。将字符串往后移动,逐个切割判断即可。这里的关键是如果判断两个子串出现的字符是一样的,我刚开始想到的解法是,分别将这两个子串进行排序,这样就可以直接比较了,但这种方法是过不了OJ的,因为当子串p特别大的时候,调用系统的sort算法是特别耗时的。最好的做法无非就是利用数组进行存储,因为字符串都是由26个小写组成,所以我们只需建立一个26个长度的序列就可以表示它们出现的情况。用数组的下标表示出现的字符,即'a'就是0,'b'就是1,......,以此类推。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int p_len = p.length();
        vector<int> res;
        if (s.length() < p_len) return res; //如果查找的子串的长度大于母串
        vector<int> s_count(26, 0);
        vector<int> p_count(26, 0);
        for (int i = 0; i < p_len; ++i){ //记录待查找字符串p的字符出现次数以及在字符串s中前p字符串长度的字符出现个数
            ++s_count[s[i]-'a'];
            ++p_count[p[i]-'a'];
        }
        if (s_count == p_count) res.push_back(0);
        for (int i = p_len; i < s.length(); ++i){
            --s_count[s[i-p_len]-'a'];
            ++s_count[s[i]-'a'];
            if (s_count == p_count)
                res.push_back(i-p_len+1);
        }
        return res;
    }
};

 滑动窗口解法:

left-----窗口的左边界,right-------窗口的右边界,cnt-----要匹配的字符总数,m------存储字符串p中字符出现的个数

当字符串s中的某段字串出现的字符和p中出现的一样时,cnt就会变成0,将左边界left记录下来;当窗口的大小大于设定的大小时,要将左边界右移,同时判断左边界出现的字符是否在p中,如果存在,去掉后,意味着要匹配的字符个数要增加1个(关键的地方)。

class Solution {
public:
    vector<int> findAnagrams(string s, string p){
        vector<int> res;
        vector<int> m(26, 0);
        for (char ch : p) ++m[ch-'a']; //记录p串中每个字符出现的次数
        int left = 0, right = 0, len = s.length(), cnt = p.length();
        
        while (right < len) { //维持的整个窗口大小为子串p的长度
            if (m[s[right++]-'a']-- >= 1) cnt--;
            if (cnt == 0) res.push_back(left); //若当前p出现的字符都被匹配,则意味着出现相同的子串
            if (right - left == p.length() && m[s[left++]-'a']++ >= 0) cnt++; //若当前窗口的大小比设定窗口大1,则左边界往右移动
        }
        return res;
    }
};

[1]https://www.cnblogs.com/grandyang/p/6014408.html

相关标签: # 滑动窗口