Leetcode.0438 | 找到字符串中所有字母异位词

Leetcode.0438 | 找到字符串中所有字母异位词 题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词：指由相同字母重排列形成的字符串（包括相同的字符串）。

示例

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

解决方法

根据“异位词”的定义，同一个单词的各个异位词之间，各个元素出现的次数是相等的。比如，"ab"和"ba"两个异位词之间，字母a和b都只出现了一次。然后，就可以用一个长度为26的数组来记录每个英文字母出现的次数。

接着，使用“滑动窗口”，设置left和right两个变量，left表示窗口的开始位置，right表示窗口的结束位置，区间[left,end]用来记录当前窗口中的元素。

在起始位置，滑动窗口的left值为0，right值为-1，此时窗口没有元素。

向右移动right，直到窗口内元素个数等于字符串p的长度。判断窗口中的内容是否是字符串p的异位词。

判断结束后，将窗口整体右移，继续判断窗口的新内容是否是p的异位词。

代码实现

class Solution {
public:
    vector findAnagrams(string s, string p) {
        int left = 0;
        int right = -1;
        vector res;
        vector sourceData(26,0);
        for(int i = 0;i < p.size();i ++){
            sourceData[p[i]-'a'] ++;
        }
        int windowLen = p.size();
        if(windowLen > s.size()) return res;
        while(right != s.size()){
            while((right-left+1) < windowLen){
                right ++;
            }
            vector targetData(26,0);
            for(int i = left;i <= right;i ++){
                targetData[s[i]-'a'] ++;
            }
            if(sourceData == targetData) //c++中可以直接比较两个vector是否相等
            {
                res.push_back(left);
            }
            left ++;
            right ++;
        }
        return res;
    }
};