个人网站源代码,做网站 推广,乐清视频制作公司,长沙网站设计公司哪家好LeetCode原题链接#xff1a;438. 找到字符串中所有字母异位词
下面是题目描述#xff1a; 给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串…LeetCode原题链接438. 找到字符串中所有字母异位词
下面是题目描述 给定两个字符串 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、解题思路 前言如果有第一次学习滑动窗口算法的朋友可以先阅读一下笔者关于滑动窗口算法的第一篇文章【算法学习】-【滑动窗口】-【长度最小的子数组】那里对滑动窗口会有较详细的讲解下面的解题思路中关于相关算法的步骤就仅进行简单的叙述啦。
由题目描述可得 本题主要可分为以下两个步骤 1判断一个字符串是否为另一个字符串的异位词 这里需要借助哈希表这个数据结构来进行判断即将两个字符串中的字符分别放入两个哈希表中然后对比这两个哈希表若两个哈希表中的字符及字符个数都一样则说明是异位词否则不是。
2确定滑动窗口 相较于之前笔者有关滑动窗口算法的文章中的滑动窗口这里的窗口大小是恒定的即用于构成窗口大小的两个指针是 “共进退” 的。故此时直接照搬之前控制窗口移动的思路反而会使情况变得复杂。下面介绍一下算法的步骤
先初始化两个哈希表便于直接进行第一次判断判断两个哈希表中的内容否相等若相等则记录索引也就是构成窗口的前面的那个指针的值接着无论是否相等都需将字符串s对应的哈希表中的第一个字符删除注意这里要先让数量--数量为0后才执行删除操作而进行下一次枚举删除后向s对应的哈希表中插入新的字符然后两个指针都向后移动一位准备进行下一次的判断。循环执行上述过程。
2、具体代码 vectorint findAnagrams(string s, string p){unordered_mapchar, int mapOfp;unordered_mapchar, int mapOfs;//初始化哈希表for (size_t i 0; i p.size(); i){mapOfp[p[i]];mapOfs[s[i]];}vectorint res;size_t cur p.size();size_t begin 0;while (cur s.size()){if (mapOfp mapOfs){res.push_back(begin);}if( --mapOfs[s[begin]] 0){mapOfs.erase(s[begin]);}begin;mapOfs[s[cur]];}if (mapOfp mapOfs){res.push_back(begin);}return res;}看完觉得有觉得帮助的话不妨点赞收藏鼓励一下有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论多多指点谢谢朋友们
