大连做网站哪家便宜,免费推广企业网站,软件产品,wordpress建站购买1. 题目链接#xff1a;438. 找到字符串中所有字母异位词
2. 题目描述#xff1a; 给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串#xff08;包括…1. 题目链接438. 找到字符串中所有字母异位词
2. 题目描述 给定两个字符串 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 的异位词。提示: 1 s.length, p.length 3 * 104s 和 p 仅包含小写字母 3. 解法滑动窗口哈希表
3.1 算法思路
因为字符串p的异位词的长度一定与字符串p的长度相同所以我们可以在字符串s中构造一个长度为与字符串p的长度相同的滑动窗口并在滑动中维护窗口中每种字母的数量当窗口中每种字母的数量与字符串p中每种字母的数量相同时则说明当前窗口为字符串p的异位词因此可以用两个大小为26的数组来模拟哈希表一个来保存s中的子串每个字符出现的个数另一个来保存p每一个字符出现的个数。这样就能判断两个串是否是异位词
3.2 算法流程
初始化hash1数组用来统计字符串p中每个字符出现的次数。初始化hash2数组用来统计滑动窗口内每个字符出现的次数。将滑动窗口的左边界left和右边界right都初始化为0。遍历字符串s从左到右依次将字符加入窗口。判断是否需要移动窗口。如果窗口长度超过了p的长度就需要移动窗口判断是否需要从窗口中移出最左边的字符。如果需要移出字符就从窗口中移出最左边的字符并更新hash2数组和count变量。判断窗口内的字符是否是p的异位词。如果是将左边界的索引加入结果数组ret。返回结果数组ret。 3.3 C算法代码
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash1[26]{0};//统计字符串p中每个字符出现的次数for(auto ch:p)hash1[ch-a];int hash2[26]{0};//统计窗口里面的每个字符出现的个数int mp.size();for(int left0,right0,count0;rights.size();right){char ins[right];if(hash2[in-a]hash1[in-a])count;//进窗口维护countif(right-left1m)//判断{char outs[left];if(hash2[out-a]--hash1[out-a])count--;//出窗口维护 count}//更新结果if(countm)ret.push_back(left); }return ret;}
};
