leetcode 438. Find All Anagrams in a String

痛定思痛。 2022-06-08 00:05 111阅读 0赞

# 1.题目 #

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

翻译：给出字符串s,p，求s中所有p中的字符随机组成的字符串的起始下标。

Example 1:

Input:  
s: “cbaebabacd” p: “abc”

Output:  
\[0, 6\]

Explanation:  
The substring with start index = 0 is “cba”, which is an anagram of “abc”.  
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

# 2.分析 #

遍历S字符串，每次取P的长度的子字符串ss,判断ss是不是由p中的字符随机颠倒组成的。

如何判断ss是不是由p中的字符随机颠倒组成的？  
即字符的构成是否相同，对出现的字符计数即可。

为了减少计算量，用滑动窗口取字符串可以该为，移动窗口，只对字符计数做改变。增加新增字符计数，减少去掉字符计数。

# 3.代码 #

vector<int> findAnagrams(string s, string p) {
        vector<int> sv(26, 0), pv(26, 0), ans;
        for (int i = 0; i < p.size(); i++) {
            ++sv[s[i] - 'a'];
            ++pv[p[i] - 'a'];
        }
        if (pv == sv)
            ans.push_back(0);
        for (int i = p.size(); i < s.size(); i++) {
            ++sv[s[i] - 'a'];
            --sv[s[i - p.size()] - 'a'];
            if (pv == sv)
                ans.push_back(i-p.size()+1);
        }
        return ans;
    }