【滑动窗口】找到字符串中所有字母异位词| 找出字符串中第一个匹配项的下标

---

找到字符串中所有字母异位词

我的思路：先将p字符串排序，然后遍历s字符串，取出p.size()大小的子串，然后进行排序，对比两个字符串是否相等即可。
注意的问题：

• 1.字符串的比较，要用strcmp，如果直接比较两个字符串的话，比较的字符串首元素地址，会出现问题。
• 2.时间复杂度太高，排序O(nlog(n))，要排序s.size（） - p.size（）次，行不通。

正确解法：

• 固定长度的滑动窗口+两个哈希表。
• 1.将p字符串的每个字符先放进p串自己的哈希表。
• 2.将s字符串的前lenp-1个字符也放进哈希表，比如p字符串为"abc"，此时将s字符串的前两个字符也放进s字符串自己的哈希表中，这样做是方便后续进行滑动窗口。
• 3.走滑动窗口三部曲即可。
• • 进窗口后，此时两个哈希表存储的字符数量就相等，遍历一遍哈希表，比较哈希表中的元素是否都相等，如果不等代表不是异位词，如果相等，则存储下标。（因为这道题要的是异位词，不是相等的字符串，所以可以直接放进哈希表中）
• • 时间复杂度O(n)*O(哈希表的大小)，哈希表的大小是26，等价于O(1)了，所以时间复杂度是O(n);

代码如下：

vector<int> findAnagrams(string s, string p) 
{if(s.size() < p.size())return {};int hashs[26] = {0},hashp[26] = {0};int np = p.size(),ns = s.size();//先把字符放进哈希表for(auto c : p ){hashp[c - 'a']++;}//同时把p字符串的前np-1个字符放进哈希表for(int i = 0;i < np-1;i++){hashs[s[i] - 'a']++;}//开始滑动窗口vector<int> v;for(int left = 0,right = np-1;right < ns;++right){//1.进窗口hashs[s[right] - 'a']++;//2.判断int i = 0;while(i < 26){if(hashs[i] != hashp[i])break;++i;}if(i >= 26)v.push_back(left);//3.出窗口hashs[s[left++] - 'a']--;}return v;
}

找出字符串中第一个匹配项的下标

解法：其实就是模拟实现C语言的strstr函数。

之前的文章讲解过了，可以搜一下。这里直接实现。

int strStr(string s, string p) {if (p.size() == 0)return -1;int si = 0, pi = 0, cur = 0;while (cur < s.size()) {while (si < s.size() && pi < p.size() && s[si] == p[pi]) {++si;++pi;}if (pi >= p.size()) // 说明找到了return cur;if (si >= s.size()) // 说明找完s字符串都没找到return -1;si = ++cur;pi = 0;}return -1;
}