黄冈网站建设策划,合肥高新城建设计院网站,seo关键词排名优化怎么样,app网页设计网站给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;。 示例 1:
输入: s cbaebabacd, p …给定两个字符串 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 仅包含小写字母
思路用一个数组count来记录p字符串中所有字母出现的次数。
然后定义 currcount数组记录滑动窗口中所有字母出现的次数。在定义该数组时先记录s字符串中前n-1个字母n为p字符串的长度的出现次数。
然后在for循环中定义滑动窗口的左指针为0右指针为p.size()-1也就是滑动窗口的最后一个字母把右指针的字母记录到currcount数组中并且判断此时currcount和count是否一致如果一致把此时的左指针添加到结果数组中。然后把左指针记录的元素从currcount数组中删除一次出现次数。因为接下来要使得整个滑动窗口往右移动一个位置所以左指针指向的元素不包含在滑动窗口内了
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ans;vectorint count(26);if(s.size()p.size())return ans;for(int i0;ip.size();i){count[p[i]-a];}vectorint curcount(26);for(int i0;ip.size()-1;i){curcount[s[i]-a];}for(int l0,rp.size()-1;rs.size();l,r){curcount[s[r]-a]; //记录滑动窗口右边新加入的元素次数if(countcurcount){ans.push_back(l);}curcount[s[l]-a]--; //删除滑动窗口左边即将要剔除的元素次数}return ans;}
};
注意记录滑动窗口中字母出现次数的数组在定义并初始化时只初始化s字符串前n-1个n为p字符串的长度字母出现次数。然后在for循环中先记录窗口右边新加入的元素最后再删除窗口左边马上出去的元素次数。很巧妙
