LeetCode 438. 找到字符串中所有字母异位词
LeetCode 438. 找到字符串中所有字母异位词
在这篇博客中，我们将讨论如何解决一道有趣的字符串问题：在给定字符串s中找到所有p的异位词的子串。首先，我们来定义异位词：
异位词：异位词是指由相同字母重排列形成的字符串，包括相同的字符串。
例如，"abc"和"bca"是异位词，"aab"和"aba"也是异位词。
问题描述
给定两个字符串s和p，我们需要找到s中所有p的异位词的子串，并返回这些子串的起始索引。我们可以采用滑动窗口的方法解决这个问题，通过维护一个固定长度的窗口，不断滑动并比较窗口内的字符频次是否与p相等。
解决方案
首先，我们检查输入是否合法。如果s为空、p为空或者s的长度小于p的长度，则直接返回空结果。
接下来，我们需要初始化两个向量sCount和pCount，它们分别用于存储字符串s和p中每个字母出现的次数。这里我们使用数组来映射字母出现的次数，数组长度为26，对应英文字母的个数。
我们遍历字符串p，统计其中每个字母出现的次数，存储在pCount中。
然后，我们开始遍历字符串s，并维护一个长度为p的滑动窗口。在遍历过程中，不断更新滑动窗口内字符的频次。如果滑动窗口的大小大于了p的长度，我们需要移除窗口的最左边的字符，并更新频次。
在每次滑动窗口后，我们比较sCount和pCount是否相等，如果相等，则表示当前窗口内的字符是p的一个异位词。我们记录当前窗口的起始索引，并将其加入结果数组中。
最后，返回结果数组。
代码实现
下面是用C++实现的解决方案代码：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result={};
//检查输入是否合法
if(s.empty()||p.empty()||s.length()<p.length()) return {};
vector<int> sCount(26,0),pCount(26,0); //用数组去映射字母出现的次数
for(auto ch:p){
pCount[ch-'a']++;
}
int pLength=p.length();
for(int i=0;i<s.length();i++){
sCount[s[i]-'a']++;
//如果滑动数组的大小大于了p的长度
if(i>=pLength){
sCount[s[i-pLength]-'a']--;
}
if(sCount==pCount){
result.push_back(i-pLength+1);
}
}
return result;
}
};
分析复杂度
-
时间复杂度：
- 遍历字符串s的过程需要O(n)的时间，其中n是字符串s的长度。
- 在遍历过程中，我们维护一个固定长度的滑动窗口，对于每个窗口，更新sCount和比较sCount与pCount的时间复杂度均为O(1)。
- 因此，整个算法的时间复杂度为O(n)，其中n是字符串s的长度。
-
空间复杂度：
- 我们使用了两个大小为26的数组sCount和pCount来存储字符出现的频次，因此空间复杂度为O(1)。
综上所述，该算法的时间复杂度为O(n)，空间复杂度为O(1)。在处理大量字符串时，该算法具有高效的表现。
总结
通过滑动窗口的方法，我们可以高效地解决寻找字符串中所有异位词的子串问题。该方法的时间复杂度为O(n)，其中n是字符串s的长度。我们通过比较字符频次来判断字符串的异位词关系，从而快速找到所有符合条件的子串。
原文地址：https://blog.csdn.net/m0_60134435/article/details/136334638
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！