力扣:438. 找到字符串中所有字母异位词 题解

发布时间:2024年01月07日

Problem: 438. 找到字符串中所有字母异位词

预备知识

image.png

此题用到了双指针算法中的滑动窗口思想,以及哈希表的运用。c++中是unordered_map。如果对此不了解的uu,建议查看相关介绍博客和更简单的题目!!!

解题思路

该题解法为:滑动窗口 + 哈希表。

  1. 该题的滑动窗口是固定的,我们只需要对每次移动新字符和删除字符进行判断,时间复杂度为O(n)。

  2. 首先,定义一个哈希表,记录要满足匹配p字符串需要多少的对应的字符。

    unordered_map<char, int> pp;
    
  3. 遍历p,出现对应的字符,就在该位置的–,说明还需要在s中找多少该字符。

    while (j < p.size()) {  //O(1) 理论上子字符串的操作应该是1
        //开始遍历,在s上初始化第一个字符串,能够满足对应字符供给的就++
        pp[s[j++]]++;
    }
    
  4. 遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到x.

    for (auto& [a, b] : pp) {   //O(1) max=26
        //遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到x
        if (b != 0) goto x;
    }
    
  5. 最后进行全局遍历

    while (j < s.size()) {  //O(n)
        //开始遍历
        //对于j位置的字符,将pp对应位置++,表示提供一个字符
        pp[s[j]]++;
        //对于i位置的字符,将pp对应位置--,表示不能提供一个字符
        pp[s[i]]--;
        for (auto& [a, b] : pp) {   //O(1) max=26
            if (b != 0) goto xx;
        }
        v.push_back(i + 1);
        xx:;
        i++;j++;
    }
    

复杂度

时间复杂度:

O(26 * n),26是遍历哈希表中的每种英文字母的个数,最多为26,n是遍历滑动窗口。

空间复杂度:

O(26 + n),26是哈希表最大size,n是vector最大size。

Code

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        //记录要满足匹配p字符串需要多少的对应的字符
        unordered_map<char, int> pp;    
        vector<int> v;
        int i = 0, j = 0;
        for (auto a : p) {  //O(n)
            //遍历p,出现对应的字符,就在该位置的--,说明还需要多少该字符
            pp[a]--;
        }
        while (j < p.size()) {  //O(1) 理论上子字符串的操作应该是1
            //开始遍历,在s上初始化第一个字符串,能够满足对应字符供给的就++
            pp[s[j++]]++;
        }
        for (auto& [a, b] : pp) {   
            //调试bug的时候可以用输出的方法
            cout << a << b << endl;
        }
        for (auto& [a, b] : pp) {   //O(1) max=26
            //遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到x
            if (b != 0) goto x;
        }
        v.push_back(i);
        x:;
        while (j < s.size()) {  //O(n)
            //开始遍历
            //对于j位置的字符,将pp对应位置++,表示提供一个字符
            pp[s[j]]++;
            //对于i位置的字符,将pp对应位置--,表示不能提供一个字符
            pp[s[i]]--;
            for (auto& [a, b] : pp) {   //O(1) max=26
                if (b != 0) goto xx;
            }
            v.push_back(i + 1);
            xx:;
            i++;j++;
        }
        return v;
    }
};

其它细节

可以尝试用输出日志的方式来获得局部代码的正确性。对于比较长的代码,我们应该在写完整个代码之前,已经完成多个地方的日志输出。多加练习能够提高自己写代码的正确性。

for (auto& [a, b] : pp) {   
    //调试bug的时候可以用输出的方法
    cout << a << b << endl;
}

推荐博客或题目

博客

  1. 滑动窗口详解
  2. 哈希表理论基础

题目

滑动窗口

  1. 无重复字符的最长子串 难度:++

哈希表

  1. 两数之和 难度:++
  2. 三数之和 难度:+++
  3. 四数之和 难度:++++
  4. 四数相和II 难度:++++
文章来源:https://blog.csdn.net/weixin_62021811/article/details/135370312
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。