• <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
            復雜度O(mn)不曉得能不能貓過,直接想了O(m+n)的
            先用字典預處理,判斷s是否一定包含t,是的話維護兩個指針pos_l和pos_r,從開頭掃到結尾,若當區(qū)間已經包含t,則更新最短結果+pos_l右移,否則pos_r右移,注意當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]
            久久国产精品77777| 久久国产免费| 久久久精品久久久久影院| 久久精品亚洲男人的天堂| 亚洲午夜精品久久久久久app| 中文字幕成人精品久久不卡 | 情人伊人久久综合亚洲| 99久久国产综合精品五月天喷水 | 久久性精品| 久久WWW免费人成一看片| 91久久精品91久久性色| 久久久久综合国产欧美一区二区| 97久久婷婷五月综合色d啪蜜芽| 国产成人精品久久免费动漫| 四虎影视久久久免费观看| 久久精品国产亚洲精品2020| 国产精品亚洲综合专区片高清久久久 | 久久国产成人午夜aⅴ影院 | 久久久久亚洲精品天堂久久久久久| 一本色道久久88综合日韩精品| 97久久香蕉国产线看观看| 久久精品亚洲乱码伦伦中文| 精品久久久久久久久中文字幕| 青青草原1769久久免费播放| 亚洲精品高清国产一线久久| 久久精品国产一区二区三区| 欧洲成人午夜精品无码区久久| 久久精品中文字幕有码| 久久免费高清视频| 久久发布国产伦子伦精品 | 久久99国产精品成人欧美| 久久久精品国产sm调教网站| 久久人人添人人爽添人人片牛牛| 国产精品成人无码久久久久久 | 久久精品国产精品青草app| 亚洲色婷婷综合久久| 伊人久久大香线蕉综合5g| 一本大道久久香蕉成人网| 亚洲欧美精品一区久久中文字幕| 久久精品成人| 久久久久亚洲精品中文字幕|