题目描述(难度中等)
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 0。
说明:
字母异位词指字母相同,但排列不同的字符串。
不考虑答案输出的顺序。
示例 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" 的字母异位词。
解题思路
利用滑动窗口:
窗口的长度是p的长度用两个哈希数组存储p的字母情况和滑动窗口的字母情况。如果二者相同,则将起始位置加入到结果中,如果不同,则将滑动窗口右移一位继续判断。
代码如下
class Solution {public:vector<int> findAnagrams(string s, string p) {vector<int> res;if(s.size()<p.size())//边界情况return res;int pn=p.size();vector<int> hash_p(256,0);//两个哈希数组存储p和滑动窗口的字母vector<int> hash_temp(256,0);for(auto c:p)//将p的字母存储起来hash_p[c]++;int left=0;//滑动窗口的左指针for(int i=0;i<s.size();i++){if(i<pn)//第一个滑动窗口{hash_temp[s[i]]++;//如果s的前p.size()字母正好是p的字母异位词,将起始位置0加入结果if(i==pn-1 && hash_p==hash_temp)res.push_back(0); }else{int k=i-pn;hash_temp[s[k]]--;//减去移动窗口后的前一个位置的字母hash_temp[s[i]]++;//加上窗口右移后新加入的字母left++;//窗口起始位置+1//如果是异位词,则将起始位置加入结果if(hash_temp==hash_p)res.push_back(left);}}return res;}};
提交结果: