找到字符串中所有字母异位词

leetcode link: 找到字符串中所有字母异位词

相似题目：有效的字母异位词

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

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

示例 1:

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

解题思路1：

• 1 按照“有效的字母异位词”这道题的做法，使用哈希表来判断两个字符串是否是字母异位词。
• 2 在1的基础上使用一个for循环遍历即可。

class Solution {
public:
    int map[26] = {0};
    bool is_same(string a, string b){
        memset(map, 0, sizeof(map));
        for(int i=0; i<b.size(); i++){
            map[b[i]-'a']++;
        }
        for(int i=0; i<a.size(); i++){
            map[a[i]-'a']--;
        }
        for(auto m:map){
            if (m!=0) return false;
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        for(int i=0; i<s.size(); i++){
            string temp = s.substr(i, p.size());
            if (is_same(temp, p)) result.push_back(i);
        }
        return result;
    }
};