滑动窗口(6)_找到字符串中所有字母异位词

个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

滑动窗口(6)_找到字符串中所有字母异位词

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌

1. 题目链接:

OJ链接:找到字符串中所有字母异位词

2. 题目描述 :

给定两个字符串 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 仅包含小写字母

3. 解法 :

    解法一(暴力枚举) :

    算法思路 :

1.用两个hash表分别存贮两个字符串,hash1存贮字符串s,hash2存贮字符串p

2.用两层循环取s中的p大小的字符串存入hash1中,然后与hash2进行比较

3.如果相等返回s取的子字符串的起始位置,不相等直接从下一个位置截取p大小的字符串继续比较

    易错警示:

1. 在遍历字符串s时需要注意边界问题,如果当s的长度小于p时,还去s中取p长度的字符串就会导致越界访问,程序报错!

2. 如果刚开始字符串s就小于p,可以直接放回空vector,不需要处理!

    代码展示 :

class Solution {

      bool check(int a[], int b[])
        {
            for(int i = 0; i < 26; i++)
                if(b[i] != a[i]) return false;
            return true;
        }
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash2[26] = {0};
        for(auto e : p) hash2[e - 'a']++;

        int slen = s.size();
        int plen = p.size();

        //如果s的长度小于p的长度直接返回空结果
        if(slen < plen) return ret;

        for(int i = 0; i <= s.size() - p.size(); i++)//确保不越界
        {
            int hash1[26] = {0};
            for(int j = 0; j < plen; j++)
                hash1[s[i + j] - 'a']++;
            if(check(hash1, hash2)) ret.push_back(i);
        }
        return ret;
    } 
};

    结果分析 :

其实这道题很出乎我的意料,我没想到两层循环的暴力也能解决,因为算法题暴力一般都解决不了.

但是我分析了一下题目给的范围我恍然大悟,题目两个字符串的长度都小于3*10^4,这个暴力算法两层遍历时间复杂度为O(N^2),总体数据级别为9*10^8 < 10^9,计算机能在1s中内完成,系统也就不会判定你超时,我们的check函数虽然也是遍历,但只遍历了26次,是常数级别,可以忽略不记,所以我们整体的代码顺利AC了这道题!

    对暴力算法的反思与优化 :

这里对暴力算法的优化很简单,没错我们的老朋友滑动窗口:

还是和之前一样的思路,我们没有必要让j直接回来,我们可以让i直接++,这样就省去了多余的遍历

    解法二(滑动窗口) :

    算法思路 :

1. 因为字符串p的异位词的长度一定与字符串p的长度相同,所以我们可以在字符串s中构造一个长度与字符串p的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量;

2. 当窗口中每种字母的数量与字符串p中每种字母的数量相同时,则说明当前窗口为字符串p的异位词;

3. 因此可以用两个大小为26的数组来模拟哈希表,一个来保存s中的字串每个字符出现的个数,另一个来保存p中每一个字符出现的个数.这样就能判断两个串是否是异位词.

    图解流程 :

    代码展示 :

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int n = p.size(), count = 0;
        int hash1[26] = {0}, hash2[26] = {0};
        for(auto ch : p) hash2[ch - 'a']++;

        for(int left = 0, right = 0; right < s.size(); right++)
        {
            if(++hash1[s[right] - 'a'] <= hash2[s[right] - 'a']) count++;

            if(right- left + 1 > n)
            {
                if(hash1[s[left++] - 'a']-- <= hash2[s[left - 1] - 'a']) count--;
            }
            if(count == n) ret.push_back(left);
        }
        return ret;
    }
};

    结果分析 :

时间复杂度: O(N)

空间复杂度: O(1)

滑动窗口在这道题中是一种效率很高的解决方法.