Find All Anagrams in a String

发表于 | 分类于

Find All Anagrams in a String

题目描述：

给定一个源字符串s,和一个目标字符串t,要求找到s中所有的片段包含t的起始位置。

例子：

具体描述见LeetCode438

解题思路：

定义源和目标字符串的哈希表，因为只包含26个字母可以直接使用vector来保存字符和对应的数量；起始代码直接判断2个字符串的长度；然后遍历较短字符，保存下字符和对应的数量；这边需要注意如果开头就想同需要把0push；然后遍历长字符的字符，每增加一个字符，需要删除上一个字符对应的数量；然后进行判断是否相等。这边其实是维持了一个窗口，记录窗口中的字符的数量，是字符串中的常见做法，需要谨记！。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> sv(26, 0);
        vector<int> pv(26, 0);
        vector<int> res;
        if (p.size() > s.size())
            return res;
        
        for (int i = 0; i < p.size(); i++){
            sv[s[i] - 'a']++;
            pv[p[i] - 'a']++;
        }//遍历较短字符串
        if (sv == pv)
            res.push_back(0);
        //起始位置
        for (int i = p.size(); i < s.size(); i++){
            sv[s[i] - 'a']++;
            sv[s[i - p.size()] - 'a']--;
            //遍历新的位置
            if (sv == pv)
                res.push_back(i - p.size() + 1);
        }
        return res;
        
    }
};