LeetCode438. 找到字符串中所有字母异位词（C++实现）
题目描述
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 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" 的字母异位词。
解题思路
这道题也没有很难解，但是方法不对一直报超出时间限制，问题就在于测试用例包含了很多单一字符的字符串的比较，特别耗时！后来采用滑动窗口的方法解决，下面详细介绍一下此方法。
首先第一步就是，初始化两个map(我使用的是map
比如说现在字符串s：0 1 2 3 4 5 6 7 下标从0至7；p包含3个字符，即plen = 3；
我们从头到尾遍历字符串s，滑动窗口的长度就是p的长度plen；
第一阶段：遍历s，从下标0到下标2，这个长度刚好是达到滑动窗口的大小。那么这个时候没有比较的必要，所以我们一个一个的把这些字符记录在tmp的map中即可。
第二阶段：达到下标2，滑动窗口满了，那么先比较一次，也就是判断tmp与um是否相等；然后下一步就要将滑动窗口向右移动了，每次移动一个字符，右边新加入的字符比如下标3，对应的字符在tmp中对应的值要加一，同时呢滑动窗口前面刚移除滑动窗口的下标0对应的字符在tmp中的值要减一。然后比价。
之后就是不断重复第二阶段上面的过程。
代码示例
class Solution {
public:vector findAnagrams(string s, string p) {vector res; if(s.size() < p.size())return res;int plen = p.size();unordered_map um;string str = "abcdefghijklmnopqrstuvwxyz";for (auto i : str)um[i] = 0;unordered_map tmp(um);for (auto x : p)um[x]++;for (int i = 0; i < s.size(); i++){if(i >= plen)//超过p的长度开始，i-plen的字符从滑动窗口删除tmp[s[i - plen]]--;tmp[s[i]]++;//每次滑动窗口向右滑动一个字符if(tmp == um)res.push_back(i - plen + 1);}return res;}
};
用数组实现比较，比较巧妙的是将数组下标0-25,表示为对应的小写字母的ASCII码值-'a'。代码如下
class Solution {
public:vector findAnagrams(string s, string p) {vector res; if(s.size() < p.size())return res;int plen = p.size();vector vp(26, 0), vtmp(26, 0);//初始化数组长度为26，每个下标值对应小写字母的ASCII码值-'a'for (auto x : p)vp[x - 'a']++;for (int i = 0; i < s.size(); i++){if(i >= plen)//超过p的长度开始，i-plen的字符从滑动窗口删除vtmp[s[i - plen] - 'a']--;vtmp[s[i] - 'a']++;//每次滑动窗口向右滑动一个字符if(vtmp == vp)res.push_back(i - plen + 1);}return res;}
};
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！