Wednesday, June 4, 2014

Minimum Window Substring

Code is shown as below. One thing I really need to notice is the mistake I made about HashMap. or more generally, the Collections of Java. When I was using .get() method, I think HashMap.get(i) is same as a variable. However, this opinion is totally wrong! If you need to change the value of HashMap.get(i), please use another variable var to store HashMap.get(i), change value of var, and put it back, i.e. HashMap.put(i,var)

public class Solution {
    public String minWindow(String S, String T) {
        if(S == null || T == null || S.length() < T.length()) return "";
       
        int SLen = S.length();
        int TLen = T.length();
       
        if(SLen == TLen ) {
            if(T.equals(S)) return S;
            // else return ""; // be careful, content might be the same, but order is different
        }
        // charAndIdx  stores the index of element of T in S
        LinkedList<DT> charAndIdx = new LinkedList<DT>();
        HashMap<Character, Integer> TMap = new HashMap<Character, Integer>();
     
        initialHM(TMap, T); // TMap is used to store the elements of T, and how many times they appear
     // However, when used in following loop, TMap stores num of crntC in T - num of crntC in charAndIdx
        int count = 0;// count is used to count the number of valid or useful elements contained in charAndIdx
        String result = null;
        for(int i = 0; i < SLen;i ++){
            char crntC = S.charAt(i);
            if(TMap.containsKey(crntC)){
                if(TLen == 1) return T;
                if(TMap.get(crntC) > 0) count ++;
                int t = TMap.get(crntC);// record how many times crntC appear until one valid window is found
                TMap.put(crntC,t - 1);
                DT dt = new DT(crntC,i);
                charAndIdx.add(dt);
               
                if(count == TLen){// one valid window is found
                   
                    DT head = charAndIdx.removeFirst();
                    int k = TMap.get(head.c);
                    TMap.put(head.c,k+1);
                    DT tail = charAndIdx.peekLast();
                    String tmpResult;
                    while(TMap.get(head.c) < 1){// If the head.c appear more than once in the valid substring
// if TMap.get(head.c) is 0, then it means all the head.c has or have been contained in the charAndIdx.
// If  TMap.get(head.c) > = 1, we should move on to find next index i where more head.c can be found, so
// that the charAndIdx contains all the letters of T, i.e. we need to get out of this while loop, and then i++
                        head = charAndIdx.removeFirst();
                        int m = TMap.get(head.c);
                        TMap.put(head.c,m+1);
                       
                    }//In this while loop, what I want is to remove one element of T, then charAndIdx should just //lack this element. This loop actually help us remove redundant elements found in charAndIdx list.  
  
                        tmpResult = S.substring(head.index,tail.index + 1);
                       
                        if (tmpResult.length() == TLen) return tmpResult;
                        if (result == null || tmpResult.length() < result.length()) result = tmpResult;
                    count --;
                }
            }
           
        }
        if(result == null) return "";
        return result;
    }
   
    public void initialHM(HashMap<Character, Integer> TMap ,String T){
        for(int i = 0; i < T.length();i++){
            if(TMap.containsKey(T.charAt(i))) {
                int j = TMap.get(T.charAt(i));
                TMap.put(T.charAt(i),j + 1);
            }
            else TMap.put(T.charAt(i),1);
        }
    }
   
}

class DT{
    public char c;
    public int index;
    DT(char x, int y){
        c = x;
        index = y;
    }
}

No comments:

Post a Comment