LeetCode : 76. Minimum Window Substring 最小窗口子串

约定不等于承诺〃 2021-06-24 16:11 388阅读 0赞

**试题**  
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”  
Note:

If there is no such window in S that covers all characters in T, return the empty string “”.  
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

**代码**  
通过一个map来记录包含的字母位置。没想到会有重复字母，导致不得不使用集合。

class Solution {
        String res = "";
        public String minWindow(String s, String t) {
            
            int cnt = 0;
            int[] cmap = new int[256];
            HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
            
            Arrays.fill(cmap,-1);
            for(char c : t.toCharArray()){
                if(cmap[c-'A']==-1) cmap[c-'A'] = 0;
                cmap[c-'A'] += 1;
            }
            
            char[] saar = s.toCharArray();
            for(int i=0; i<saar.length; i++){
                int temp = saar[i]-'A';
                if(cmap[temp]>0){
                    cnt += 1;
                    cmap[temp]--;
                    if(map.containsKey(temp)){
                        map.get(temp).add(i);
                    }else{
                        ArrayList<Integer> newt =  new ArrayList<Integer>();
                        newt.add(i);
                        map.put(temp, newt);
                    }
                }else if(cmap[temp]==0){
                    map.get(temp).add(i);
                    map.get(temp).remove(0);
                }
                if(cnt==t.length()){
                    findmm(map, s);
                }
            }
            return res;
        }
    
        public void findmm(HashMap<Integer,ArrayList<Integer>> map, String s){
            int min=s.length(),max=-1;
            for(int ind : map.keySet()){
                ArrayList<Integer> temp = map.get(ind);
                for(int i : temp){
                    min = Math.min(min, i);
                    max = Math.max(max, i);
                }
            }
            if(res.equals("") || max-min+1<res.length()){
                res = s.substring(min, max+1);
            }
        }
    }