題目描述

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

For example,
S = <font color=red>“ADOBECODEBANC</font><br />
T = <font color=red>“ADOBECODEABCBANC</font><br />
Minimum window is "BANC"

原題鏈接

解題思路

建立一個(gè)字典宁舰，然后維護(hù)一個(gè)窗口倔韭。在移窗的時(shí)候可以跳過(guò)沒(méi)在字典里面的字符（也就是這個(gè)串不需要包含且僅僅包含字典里面的字符，有一些不在字典的仍然可以滿足要求），只要遇到?jīng)]在字典里面的字符可以繼續(xù)移動(dòng)窗口右端聪富，而移動(dòng)窗口左端的條件是當(dāng)找到滿足條件的串之后，一直移動(dòng)窗口左端直到有字典里的字符不再在窗口里二跋。

在實(shí)現(xiàn)中就是維護(hù)一個(gè)HashMap木人，一開(kāi)始key包含字典中所有字符，value就是該字符的數(shù)量钠绍，然后遇到字典中字符時(shí)就將對(duì)應(yīng)字符的數(shù)量減一舆声。算法的時(shí)間復(fù)雜度是O(n),其中n是字符串的長(zhǎng)度，因?yàn)槊總€(gè)字符再維護(hù)窗口的過(guò)程中不會(huì)被訪問(wèn)多于兩次柳爽∠蔽眨空間復(fù)雜度則是O(字典的大小)，也就是代碼中T的長(zhǎng)度泻拦。代碼如下：

需要注意一些的細(xì)節(jié)是：

1. count只有在char的個(gè)數(shù)>= 0是才++毙芜， 因?yàn)橛锌赡苷业降男碌淖址麑儆谧值洌菙?shù)量已經(jīng)匹配完但是整個(gè)字符串尚未滿足要求

2. 同理在逆向操作的時(shí)候只有個(gè)數(shù) > 0時(shí)才count --

Java代碼實(shí)現(xiàn)

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0) {  
            return "";  
        }
        
        Map<Character, Integer> map = new HashMap<>();  
        for (int i = 0; i < t.length(); i++)  {  
            if (map.containsKey(t.charAt(i))) {  
                map.put(t.charAt(i), map.get(t.charAt(i)) + 1);  
            } else {  
                map.put(t.charAt(i), 1);  
            }  
        }  
        int left = 0; // start of the window
        int count = 0; // count of the letters matched in map
        int minLen = s.length() + 1;
        int minStart = 0; //start index of the final result
        
        for (int right = 0; right < s.length(); right ++) {
            char curChar = s.charAt(right);
            if (map.containsKey(curChar)) {
                map.put(curChar, map.get(curChar) - 1);  
                if (map.get(curChar) >= 0) {  
                    count ++;  
                }  
                while (count == t.length()) {
                    char leftChar = s.charAt(left);
                    if (right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        minStart = left;
                    }
                    if (map.containsKey(leftChar)) {  
                        map.put(leftChar, map.get(leftChar) + 1);  
                        if (map.get(leftChar) > 0) {  
                            count--;  
                        }  
                    }
                    left ++;
                }
            }
        }
        
        String result;
        if (minLen > s.length()) {
            result = "";
        } else {
            result = s.substring(minStart, minStart + minLen);
        }
        return result;
    }
}