Find All Anagrams in a String 找变位子串

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

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.

The order of output does not matter.

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".

Example 2:

Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

本题难度为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;
}

Find All Anagrams in a String 找变位子串

相关推荐