自学内容网 自学内容网

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;
    }
};

分析复杂度

  1. 时间复杂度

    • 遍历字符串s的过程需要O(n)的时间,其中n是字符串s的长度。
    • 在遍历过程中,我们维护一个固定长度的滑动窗口,对于每个窗口,更新sCount和比较sCount与pCount的时间复杂度均为O(1)。
    • 因此,整个算法的时间复杂度为O(n),其中n是字符串s的长度。
  2. 空间复杂度

    • 我们使用了两个大小为26的数组sCount和pCount来存储字符出现的频次,因此空间复杂度为O(1)。

综上所述,该算法的时间复杂度为O(n),空间复杂度为O(1)。在处理大量字符串时,该算法具有高效的表现。

总结

通过滑动窗口的方法,我们可以高效地解决寻找字符串中所有异位词的子串问题。该方法的时间复杂度为O(n),其中n是字符串s的长度。我们通过比较字符频次来判断字符串的异位词关系,从而快速找到所有符合条件的子串。


原文地址:https://blog.csdn.net/m0_60134435/article/details/136334638

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!