建设网站企业网上银行,泸州作网站建设联系电话,网站建设下什么费用,工程资质题目#xff1a;
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的
异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cb…题目
给定两个字符串 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 的异位词。
分析
借鉴了力扣49题的思路拼接p中字符和字符出现次数来作为判断异位词的条件。从头开始遍历计算s字符串中当前下标以及当前下标p.length()-1之间字符的出现次数进行拼接与p的拼接结果进行比较相同则保存当前下标。
这种方法虽然能通过但是太慢每次都要拼接都要进行一个26次的循环。
改进
49题进行拼接是因为要在一堆字符串中找出其中的异位词组所以要用拼接的结果作为unordered_map的键值去和异位词做映射保存拼接结果与键值相同的异位词。这题并不不需要题目已经给出要找的字符串所以直接比较字符出现次数就行。
采用滑动窗口由于已经给出要查找的字符串那么滑动窗口的大小就确定是p的长度。在s和p中都先从头开始计算窗口大小字符串中字符的出现次数保存在数组scount,pcount中字符与下标映射。然后s开始滑动将窗口的首元素滑出同时改变数组中该字符对应下标的元素的值-1然后将新字符加入滑动窗口同理改变scount数组中该字符对应下标的元素的值1。滑动完一次比较一次sount数组与pcount数组,相同则将窗口首元素在字符串中对应的下标保存。
代码
class Solution {public:vectorint findAnagrams(string s, string p) {vectorintres;vectorintscount(26);vectorintpcount(26);for(int i0;ip.length();i){scount[s[i]-a];pcount[p[i]-a];}if(scountpcount){res.push_back(0);}for(int i0;i(s.length()-p.length());i){//移除滑动窗口队头增加新元素--scount[s[i]-a];scount[s[ip.length()]-a];if(scountpcount){res.push_back(i1);}}return res;}};
