算法练习：438. 找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词

我们来分析这个题目，题目意思就是，在s字符串中寻找包含p的异位次的字串，字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

那我们来看看如何解出这题

暴力解法：把p放入哈希表中，依次枚举s字串进行比较，时间复杂度是O(N平方)，这种解法会超时。

在暴力解法的前提下进行对其优化：

优化：不用依次枚举，当哈希表个数超了，只需要删除第一个数，不需要从头再开始遍历

同向进行移动，就可以利用滑动窗口思想：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        map<char, int> m1;
        map<char, int> m2;
        vector<int> n;
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < p.size(); i++)
        {
            m1[p[i]]++;
            sum1++;
        }
        for (int left=0, right = 0; right < s.size(); right++)
        {
            m2[s[right]]++;
            sum2++;
            if (sum1 == sum2)
            {
                auto it1 = m1.begin();
                auto it2 = m2.begin();
                while (it1 != m1.end() && it2 != m2.end())
                {
                    if ((it1->first != it2->first)|| (it1->second != it2->second))
                    break;
                    it1++;
                    it2++;
                }
                if (it1 == m1.end()) n.push_back(left);
                left++;
                sum2--;
                m2[s[left - 1]]--;
                if(m2[s[left - 1]]==0)
                m2.erase(s[left - 1]);
            }

        }
        return n;
    }
};

还可以进行优化，可以用数组来模拟哈希表，减少了消耗：

class Solution {
public:
    bool check(int *h1,int *h2)
    {
        int i = 0;
        while(i<26)
        {
            if(*(h1 + i) != *(h2 + i)) return false;
            i++;
        }
        return true;
    }
    
    vector<int> findAnagrams(string s, string p) {
        int h1[26] = {0};
        for(auto e: p) h1[e-'a']++;
        int h2[26] = {0};
        vector<int> n;
        for(int left = 0,right = 0;right < s.size();right++)
        {
            h2[s[right]-'a']++;
            if(right-left+1 > p.size())
            {
                h2[s[left]-'a']--;
                left++;
            }
            if(check(h1,h2))
            {
                n.push_back(left);
            }
        }
        return n;
    }
};

我们还可以对更新条件进行优化，定义一个变量count，来记录有效个数

这样我们就可以一边进行插入，移除，一边维护count，从而可以确定什么时候来更新 

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int h1[26] = {0};
        for(auto e: p) h1[e-'a']++;
        int h2[26] = {0};
        vector<int> n;
        for(int left = 0,right = 0,count = 0;right < s.size();right++)
        {
            //h2[s[right]-'a']++;
            if(++h2[s[right]-'a'] <= h1[s[right]-'a']) count++;
            if(right-left+1 > p.size())
            {
                if(h2[s[left]-'a']-- <= h1[s[left]-'a']) count--;
                //h2[s[left]-'a']--;
                left++;
            }
            if(count == p.size())
            {
                n.push_back(left);
            }
        }
        return n;
    }
};

原文地址：https://blog.csdn.net/2302_80652761/article/details/143822907

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