• 【每日一题】找到字符串中所有字母异位词


    题目:

    找到字符串中所有字母异位词在这里插入图片描述


    思路:

    暴力枚举:

    对于有关子串的题目我们使用暴力枚举都是比较轻易做出来的

    但是我们注意到此题寻找的是字母异位词,并不是顺序的,所以我们可以使用哈希表来进行解决这个问题。

    我们先创建一个hash1存储p的数据
    在创建一个hash2来存放遍历s的数据
    在这里插入图片描述
    因为对于这题来说暴力算法肯定是超时的,所以我们只讲述思路,
    但是这个思路是非常重要的。

    滑动窗口:

    我们可以通过暴力解法来优化得到滑动窗口。
    在这里插入图片描述
    知道可以使用滑动窗口来做题我们便可以使用滑动窗口的模板来做题。
    在这里插入图片描述

    代码实现:

    class Solution {
    public:
        bool check(int* hash1, int* hash2)
        {
            for(int i = 0; i < 26; i++)
                if(hash1[i] != hash2[i])    return false;
            return true;
        }
    
        vector<int> findAnagrams(string s, string p) {
            int hash1[26] = { 0 };
            for(auto ch : p)    hash1[ch - 'a']++;
    
            int hash2[26] = { 0 };
            vector<int> ans;
            for(int left = 0, right = 0; right < s.size(); right++)
            {
                //进窗口
                char in = s[right];
                hash2[in - 'a']++;
                //判断
                while(right - left + 1 > p.size())
                {
                    char out = s[left++];
                    hash2[out - 'a']--;
                }
                //更新结果
                if(check(hash1, hash2)) ans.push_back(left);
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    一些优化:

    我们发现,每次判断是否要更新结果时都要判断26次,
    虽然时间复杂度依旧是O(N),但是我们可以优化一下这个地方。

    如何进行优化呢?
    我们增加一个计数器,这个计数器用来存放当前窗口有效的元素个数,然后在我们判断是否更新时只需要比较count与p的长度即可。
    当然,这个count维护的地方也有一些细节

    • 入窗口后维护
    • 出窗口前维护

    代码实现:

    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            int hash1[26] = { 0 };
            for(auto ch : p)    hash1[ch - 'a']++;
    
            int hash2[26] = { 0 };
            vector<int> ans;
            for(int left = 0, right = 0, count = 0; right < s.size(); right++)
            {
                //进窗口
                char in = s[right];
                if(++hash2[in- 'a'] <= hash1[in - 'a'])  count++;
                //判断
                while(right - left + 1 > p.size())
                {
                    char out = s[left++];
                    if(hash2[out- 'a']-- <= hash1[out - 'a'])   count--;
                }
                //更新结果
                if(count == p.size()) ans.push_back(left);
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
  • 相关阅读:
    项目开发与设计流程
    MySQL之MHA集群
    人工智能 | ShowMeAI资讯日报 #2022.06.30
    如何使用CodeceptJS、Playwright和GitHub Actions构建端到端测试流水线
    WPF ObservableCollection 和 BindingList 有什么区别
    WPF中的绑定知识详解(含案例源码分享)
    PHP安全问题:远程溢出、DoS、safe_mode绕过漏洞
    OpenFeign的三种远程调用方式
    [NepCTF2022] 复现
    阿里云安全中心需要购买吗?功能及价格告诉你值不值!
  • 原文地址:https://blog.csdn.net/2301_78636079/article/details/136430380