题目描述
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
样例
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
算法1
哈希表+双指针
1、j扫描到当前的字符,如果其出现次数小于heap2中的次数,则将其出现次数加加,再进行判断该位置是否为结束字符(当前字符出现次数和heap2相等时,再进行该子串的长度判断,如果都相等,则证明为一个字母异位词)。如果是结束字符,则将起始位置放入答案中,并将该子串每个字符出现次数在heap1中清空
2、如果其出现次数和heap2中的次数相等,同时p中该字符是存在的,即表示该字符出现次数过多,需要删除该字符在前面多出现的次数,因此删除该字符及其前面的字符
3、如果其出现次数和heap2中的次数相等,但p中该字符不存在,即heap1和heap2中该字符出现次数都为0(初始化为0),此时该字符之前的字串都不再有可能成为答案,因此将其及其前面的字符都删掉,同时移动指针i,方便寻找下一个答案
小技巧:在哈希表中进行删除时,可以采用某个条件(删除的字符符合什么样的条件)进行判断,同时在判断中写入类似于heap1[s[i++]]--
这样的代码进行删除。
eg: while(heap1[s[j]]!=heap2[s[j]]-1) heap1[s[i++]]--;
eg: while(i<j) heap1[s[i++]]--;
时间复杂度
时间复杂度:两个指针都只会遍历一遍,即O(2n),即O(n)
空间复杂度:两个哈希表,即O(2n),即O(n)
C++ 代码
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> res;
// 记录p的长度,以便后续判断
int nSize = p.size();
unordered_map<char, int> heap2; // heap2记录p每个字符出现的次数
for (int i = 0; i < nSize; i++)
heap2[p[i]]++;
unordered_map<char, int> heap1; // heap1记录s每个字符出现的次数
// 双指针:i表示该子串的起始位置,j表示该子串的结束位置
for (int j = 0, i = 0; j < s.size(); j++) {
if (heap1[s[j]] < heap2[s[j]] || heap2[s[j]]&&heap1[s[j]] == heap2[s[j]] ) {
if(heap1[s[j]] == heap2[s[j]])
{
while(heap1[s[j]]!=heap2[s[j]]-1) heap1[s[i++]]--;
}
++heap1[s[j]];
if (heap1[s[j]] == heap2[s[j]]) {
if (j - i + 1 == nSize) {
res.push_back(i);
heap1[s[i++]]--;
}
}
}
else
{
while(i<j) heap1[s[i++]]--;
i++;
}
}
return res;
}
};
算法2
blablabla
时间复杂度
参考文献
C++ 代码
blablabla