唐山建网站公司,雄县哪做网站,国外推广网站有什么,谷歌广告代理商题目#xff1a;
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;。 示例 1:
输入: s cbaebabac…题目
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。 示例 1:
输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cba, 它是 abc 的异位词。
起始索引等于 6 的子串是 bac, 它是 abc 的异位词。示例 2:
输入: s abab, p ab
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 ab, 它是 ab 的异位词。
起始索引等于 1 的子串是 ba, 它是 ab 的异位词。
起始索引等于 2 的子串是 ab, 它是 ab 的异位词。提示:
1 s.length, p.length 3 * 104s 和 p 仅包含小写字母
算法原理
字符串 p 的异位词的长度⼀定与字符串 p 的长度度相同且异位词每种字母的个数和字符串每种字母的个数相同所以我们可以利用滑动窗口同向双指针构造一个长度和字符串p相同的滑动窗口并在滑动中维护窗⼝中每种字母的数量 两个数组来模拟哈希表hash1数组统计字符串p所有字母个数 hash2数组统计窗口中所有字母的个数
1 count变量来统计窗口中有效字母的个数所谓有效字母就是某个字母加入窗口后它的个数字符串p中同字母的个数那么count
2 left0左边界 right0指向待加入窗口中的元素)
3 进窗口维护counthash2数组为right指向的字母计算上一次个数 如果该字母加入窗口后此字母的个数hash1数组中同字母的个数 则count 4 判断是否出窗口维护count 如果当前窗口的长度超过字符串p的长度则要出窗口只需要出一个元素 在出窗口之前要判断出窗口的字母是否为有效字母若为有效字母 则count-- 出窗口出窗口的此字母在hash2数组中的个数-1同时left
5 更新结果若是有效字母的个数字符串p的长度则该滑动窗口构成的是异位词
代码实现
class Solution
{
public:vectorint findAnagrams(string s, string p) {int hash1[26] {0};//统计字符串p中每个字符出现的个数for(auto e:p){hash1[e-a];}int hash2[26] {0};//统计窗口里每个字符出现的个数int left 0;int right 0;int n s.size();int m p.size();int count 0;vectorint ret;while(rightn){hash2[s[right]-a];//进窗口维护countif(hash2[s[right]-a]hash1[s[right]-a]){count;}if(right-left1m)//判断{if(hash2[s[left]-a]--hash1[s[left]-a])//出窗口维护count{count--;}left;}if(countm)//更新结果{ret.push_back(left);}right;}return ret;}
};
