本文主要是介绍LeetCode 算法:找到字符串中所有字母异位词c++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题链接🔗:找到字符串中所有字母异位词
难度:中等⭐️⭐️
题目
给定两个字符串 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_map>class Solution {
public:std::vector<int> findAnagrams(const std::string& s, const std::string& p) {std::vector<int> result;if (s.size() < p.size()) return result; // 如果s的长度小于p的长度,不可能有异位词// 用于存储p中字符的频率std::unordered_map<char, int> pFreq;for (char c : p) {pFreq[c]++;}// 用于存储当前窗口的字符频率std::unordered_map<char, 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_map<char, int>& pFreq,const std::unordered_map<char, 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::vector<int> 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
这篇关于LeetCode 算法:找到字符串中所有字母异位词c++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!