Leetcode 76 Minimum Window Substring. (最小窗口子字符串) (滑动窗口, 双指针)

标签：++i   char   lis   lex   tar   string   amp   length   har   

** Leetcode 76 **

问题描述

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

例子

Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

解决方案

** Solution Java Method one **
** 3ms, beats 92.14% **
** 39.8MB, beats 46.81% **
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || s.length()  0)
                --count;
            --map[sArray[end]];
            while (count == 0) {
                if (end - start + 1  0)
                    ++count;
                ++start;
            }
        }
        if (minStart + minLength > sArray.length) 
            return "";
        return s.substring(minStart, minStart + minLength);
    }
}

** Solution Java Method Two **
** 12ms, 68.18% **
** 39.8MB, 46.81% **
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || s.length()  map = new HashMap();
        char[] tArray = t.toCharArray();
        char[] sArray = s.toCharArray();
        for(char chr : tArray)
            map.put(chr, map.getOrDefault(chr, 0) + 1);
        
        int count = tArray.length;
        int minStart = 0, minLength = Integer.MAX_VALUE;
        int start = 0;
        
        for(int end = 0; end  0)
                        ++count;
                }
                ++start;
            }
        }
        if (minStart + minLength > sArray.length) 
            return "";
        return s.substring(minStart, minStart + minLength);
    }
}

** Solution Python3 **
** 96ms, beats 86.89% **
** 13.3MB, beats 61.11% **
class Solution:
    def minWindow(self, s, t):
        need, missing = collections.Counter(t), len(t)
        i = I = J = 0
        for j, c in enumerate(s, 1):
            missing -= need[c] > 0
            need[c] -= 1
            if not missing:
                while need[s[i]] 

Leetcode 76 Minimum Window Substring. (最小窗口子字符串) (滑动窗口, 双指针)

标签：++i   char   lis   lex   tar   string   amp   length   har   

原文地址：https://www.cnblogs.com/willwuss/p/12276083.html