临沂法律网站开发公司,电脑系统做的好的网站好,工信部申诉备案网站,重庆发布微信公众号原题链接#x1f517;#xff1a;找到字符串中所有字母异位词 难度#xff1a;中等⭐️⭐️
题目
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符…原题链接找到字符串中所有字母异位词 难度中等⭐️⭐️
题目
给定两个字符串 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 * 104 s 和 p 仅包含小写字母
题解
滑动窗口法
题解 理解异位词两个字符串是异位词意味着它们包含相同的字符并且每个字符出现的次数也相同但是字符的排列顺序可以不同。 滑动窗口使用滑动窗口的方法来遍历字符串 s窗口的大小与字符串 p 的长度相等。 字符计数使用哈希表unordered_map来记录字符串 p 中每个字符的出现次数。 窗口内字符匹配在滑动窗口的过程中使用另一个哈希表来记录当前窗口内的字符及其出现次数并与 p 中的字符计数进行比较。 更新窗口每次向右移动窗口时添加新的字符到窗口的哈希表中并从窗口中移除一个字符。 判断异位词如果在某个时刻当前窗口内的字符计数与 p 中的字符计数相匹配则说明找到了一个异位词记录此时窗口的起始索引。 继续滑动继续滑动窗口直到遍历完整个字符串 s。 返回结果返回所有找到的异位词子串的起始索引列表。 复杂度时间复杂度 O(n * m)空间复杂度 O(m)。代码过程 初始化一个哈希表 pCount 来存储 p 中字符的出现次数。 初始化两个指针 left 和 right分别指向当前考虑的窗口的起始和结束位置。 使用一个哈希表 windowCount 来存储当前窗口内的字符计数。 扩展窗口直到窗口的大小等于 p 的长度。 当窗口大小等于 p 的长度时检查当前窗口是否是 p 的异位词 如果是记录下 left 指针的位置因为这是子串的起始索引。移动 right 指针来扩展窗口并更新 windowCount。 移动left 指针来收缩窗口并更新 windowCount。 重复步骤 5 和 6直到 right 指针遍历完整个字符串 s。 返回记录的所有起始索引。 c demo
#include iostream
#include vector
#include string
#include unordered_mapclass Solution {
public:std::vectorint findAnagrams(const std::string s, const std::string p) {std::vectorint result;if (s.size() p.size()) return result; // 如果s的长度小于p的长度不可能有异位词// 用于存储p中字符的频率std::unordered_mapchar, int pFreq;for (char c : p) {pFreq[c];}// 用于存储当前窗口的字符频率std::unordered_mapchar, int windowFreq;int left 0, right 0; // 左右指针定义当前窗口int validChars 0; // 当前窗口中与p中字符匹配的字符数量// 窗口大小小于p时继续扩展窗口while (right s.size() right - left p.size()) {char c s[right];if (pFreq.find(c) ! pFreq.end()) {windowFreq[c];}right;}// 当窗口大小等于p时开始检查是否为异位词while (right - left p.size()) {// 如果当前窗口是p的异位词记录起始索引if (isAnagram(pFreq, windowFreq)) {result.push_back(left);}// 移动窗口char leftChar s[left];if (pFreq.find(leftChar) ! pFreq.end()) {if (windowFreq[leftChar] pFreq[leftChar]) {validChars--;}windowFreq[leftChar]--;if (windowFreq[leftChar] pFreq[leftChar]) {validChars;}}left;// 扩展窗口if (right s.size()) {char rightChar s[right];if (pFreq.find(rightChar) ! pFreq.end()) {windowFreq[rightChar];if (windowFreq[rightChar] pFreq[rightChar]) {validChars--;}}right;}}return result;}private:// 辅助函数用于比较两个字符计数映射是否相等bool isAnagram(const std::unordered_mapchar, int pFreq,const std::unordered_mapchar, int windowFreq) {for (const auto kv : pFreq) {if (kv.second ! windowFreq.at(kv.first)) {return false;}}return true;}
};int main() {Solution solution;std::string s cbaebabacd;std::string p abc;std::vectorint anagramIndices solution.findAnagrams(s, p);std::cout Start indices of anagrams of \ p \ in \ s \ are: std::endl;for (int index : anagramIndices) {std::cout index std::endl;}return 0;
}输出结果 Start indices of anagrams of “abc” in “cbaebabacd” are: 0 6
