Re: [閒聊] 每日LeetCode

[oin1104 (是oin的說)]

今天的題目：

在s字串裡面找到包含t字串的最短字串

包含是只要有出現裡面的字母就好

順序不管



解法：

直接two pointer sliding window 什麼的

全部加起來然後全部看一下

就過ㄌ

後來發現我應該可以在縮小 l 左界

的時候用while直接縮到最小

不過好懶捏

姆咪


class Solution {
public:
    string minWindow(string s, string t)
    {
        int len = s.size();
        int lent = t.size();
        int save[300] = {};
        int tar[300] = {};

        int anslen = 99999999;
        int ansp = -1;

        for(int i = 0 ; i < lent ; i ++)
        {
            tar[t[i]] ++;
        }

        int l = 0 ;
        int r = 0 ;

        save[s[r]] ++;

        while(r != len)
        {
            int cnt = 0;
            int ok = 1;
            for(int c = 0 ; c <300 ; c ++)
            {
                cnt += save[c];
                if(save[c] < tar[c])
                {
                    ok = 0;
                }
            }

            if(ok == 0)
            {
                r++;
                save[s[r]] ++;
            }
            else if(ok == 1)
            {
                //printf("%d %d \n",l ,r);
                if(cnt < anslen)
                {
                    anslen = cnt;
                    ansp = l;
                }

                save[s[l]]--;
                l++;
            }


        }

        string ans;
        if(ansp != -1)
        {
            ans = s.substr(ansp, anslen);
        }
        //printf("ansp = %d , anslen = %d ", ansp , anslen);

        return ans;

    }
};




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.30.206 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707024995.A.BC9.html
→ kazunerae: int ok = 1
推 SecondRun: 大師