• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            復(fù)雜度O(mn)不曉得能不能貓過,直接想了O(m+n)的
            先用字典預(yù)處理,判斷s是否一定包含t,是的話維護(hù)兩個指針pos_l和pos_r,從開頭掃到結(jié)尾,若當(dāng)區(qū)間已經(jīng)包含t,則更新最短結(jié)果+pos_l右移,否則pos_r右移,注意當(dāng)pos_r移動到最右端時并不能立刻停止,因為pos_l或許可以繼續(xù)右移,得到更短的答案

            因為各種腦殘沒考慮到的case WA了7次才過。。。

             1 #76
             2 #Runtime: 302 ms
             3 #Memory Usage: 14 MB
             4 
             5 class Solution(object):
             6     def minWindow(self, s, t):
             7         """
             8         :type s: str
             9         :type t: str
            10         :rtype: str
            11         """
            12         dict_s ={}
            13         for i in s:
            14             if i not in dict_s:
            15                 dict_s[i] = 1
            16             else:
            17                 dict_s[i] += 1
            18         dict_t ={}
            19         for i in t:
            20             if i not in dict_t:
            21                 dict_t[i] = 1
            22             else:
            23                 dict_t[i] += 1
            24             if i not in dict_s:
            25                 return ""
            26             if dict_s[i] < dict_t[i]:
            27                 return ""
            28         pos_l = 0
            29         pos_r = 0
            30         tp_len_t = len(t)
            31         ans_l = 0
            32         ans_r = len(s)
            33         min_len = len(s)
            34         while pos_r < len(s) or tp_len_t <= 0:
            35
            36             if tp_len_t > 0:
            37                 if s[pos_r] in dict_t:
            38                     dict_t[s[pos_r]] -= 1
            39                     if dict_t[s[pos_r]] >= 0:
            40                         tp_len_t -= 1
            41                 pos_r += 1
            42             else:
            43                 if min_len > pos_r - pos_l:
            44                     ans_l = pos_l
            45                     ans_r = pos_r
            46                     min_len = ans_r - ans_l
            47                 if s[pos_l] in dict_t:
            48                     dict_t[s[pos_l]] += 1
            49                     if dict_t[s[pos_l]] > 0:
            50                         tp_len_t += 1
            51                 pos_l += 1
            52                 
            53         return s[ans_l : ans_r]
            欧美国产精品久久高清| 无码人妻久久一区二区三区蜜桃 | 亚洲精品乱码久久久久66| 综合久久给合久久狠狠狠97色| 一本一道久久a久久精品综合 | 国内精品久久久久影院一蜜桃 | 成人a毛片久久免费播放| 精品视频久久久久| 伊人久久大香线蕉AV色婷婷色| 国产成人精品免费久久久久| 久久本道久久综合伊人| 蜜臀av性久久久久蜜臀aⅴ | 日本精品久久久久影院日本| 久久久无码精品亚洲日韩按摩| 久久99精品国产麻豆宅宅| 亚洲狠狠综合久久| 久久午夜福利无码1000合集| 一本大道久久a久久精品综合| 久久精品无码免费不卡| 国产精品美女久久久久| 欧美激情一区二区久久久| 中文精品久久久久国产网址 | 久久久久亚洲Av无码专| 久久这里的只有是精品23| 精品久久久久久无码免费| 亚洲AV无码久久精品色欲 | 无遮挡粉嫩小泬久久久久久久| 国产精品va久久久久久久| 久久99毛片免费观看不卡 | 中文字幕久久亚洲一区| 99久久精品免费观看国产| 国产精品久久久久久久久| 蜜臀av性久久久久蜜臀aⅴ麻豆 | 欧美午夜A∨大片久久 | 欧美伊人久久大香线蕉综合69| 久久综合狠狠综合久久激情 | 久久综合给久久狠狠97色| 精品多毛少妇人妻AV免费久久| 色8激情欧美成人久久综合电| 国产精品欧美久久久久天天影视| 青青草原综合久久大伊人精品|