专栏首页算法修养LeetCode 76. Minimum Window Substring

LeetCode 76. Minimum Window Substring

题目

从第一个字符串中找到最小的子串,让子串中包含第二个字符串中的每一个字符。

我的思路来自滑动窗口思想,之前用来做自动摘要的。

把第一个字符串中的在第二个字符串中出现的字符都标记出来,找到第一个符合条件的区间。也就是第一个窗口。

然后依照之前的标记下标,开始滑动,区间左边每次进一格,右边一直寻找到满足条件的下边,一次滑动的过程就结束了。

在这个过程中寻找最小值。

一遍过。

class Solution {
public:
    map<int,int> m;
    map<int,int> m2;
    map<int,int> m3;
    int pos[100005];
    string minWindow(string s, string t) {

        int count=0;

        for(int i=0;i<t.length();i++)
        {
            if(m[t[i]]==0)
                count++;
            m[t[i]]++;
        }


        int start=-1;
        int end=-1;
        int tag=0;
        for(int i=0;i<s.length();i++)
        {
            if(m[s[i]]!=0)
            {
                m2[s[i]]++;
                pos[tag++]=i;
                if(start==-1)
                    start = tag-1;

                if(m2[s[i]]==m[s[i]]&&m3[s[i]]==0&&count>0)
                {
                    m3[s[i]]=1;
                    count--;
                }

                if(end==-1&&count==0)
                {
                    end=tag-1;
                }
            }
        }

        if(start==-1||end==-1)
            return "";

        int x = start;
        int y = end;
        int ansx = pos[x];
        int ansy = pos[y];
        int ans = pos[y]-pos[x]+1;

        m2.clear();

        for(int i=x;i<=y;i++)
        {
            m2[s[pos[i]]]++;
        }

        for(int i=1;i<tag;i++)
        {
            m2[s[pos[x]]]--;
            if(m2[s[pos[x]]]>=m[s[pos[x]]])
            {
                x=i;

                if(ans > pos[y]-pos[x]+1)
                {
                    ansx=pos[x];
                    ansy=pos[y];
                    ans = pos[y]-pos[x]+1;
                }

            }
            else
            {
                int tag2=0;
                for(int j=y+1;j<tag;j++)
                {
                    m2[s[pos[j]]]++;
                    if(s[pos[j]]==s[pos[x]])
                    {
                        if(ans > pos[j] - pos[i] +1)
                        {
                            ansx=pos[i];
                            ansy=pos[j];
                            ans = pos[j]-pos[i]+1;
                        }

                        x=i;
                        y=j;
                        tag2=1;
                        break;
                    }
                }

                if(tag2==0)
                    break;
            }
        }

        string res="";
        for(int i=ansx;i<=ansy;i++)
        {
            res+=s[i];
        }

        return res;

    }
    
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 307. Range Sum Query - Mutable

    ShenduCC
  • LeetCode 189. Rotate Array

    用O(1)空间的算法去解决。找到nums[x]旋转之后对应的位置,交换二者,然后得到的数字再找下去。知道找到一开始的数字,形成一个闭环了,然后x++,直到交换次...

    ShenduCC
  • LeetCode 224. Basic Calculator

    ShenduCC
  • BZOJ 1012: [JSOI2008]最大数maxnumber【线段树单点更新求最值,单调队列,多解】

    1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 103...

    Angel_Kitty
  • LeetCode 307. Range Sum Query - Mutable

    ShenduCC
  • LeetCode 189. Rotate Array

    用O(1)空间的算法去解决。找到nums[x]旋转之后对应的位置,交换二者,然后得到的数字再找下去。知道找到一开始的数字,形成一个闭环了,然后x++,直到交换次...

    ShenduCC
  • 【每日一题】用筛法求之N内的素数。

    题号:1084 题目描述 用筛法求之N内的素数。 输入 N 输出 0~N的素数 样例输入 100 样例输出 2 3 5 7 11 13 17 19 23 29 ...

    编程范 源代码公司
  • LeetCode 每日一题169: 求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    benny
  • 【专知-关关的刷题日记17】Leetcode 268. Missing Number

    题目 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find...

    WZEARW
  • golang进度条

    进度条元素 ▪ 总量 ▪ 当前进度 ▪ 耗时 通过以上元素可以延伸出:完成百分比、速度、预计剩余时间、根据设置速度快慢阈值用不同的颜色来显示进度条。 实现 进度...

    李海彬

扫码关注云+社区

领取腾讯云代金券