My java solution


  • 0
    public class Solution {
        public String minWindow(String s, String t) {
            if(s == null || t == null || t.length()>s.length() ) return "";
            Node[] criteria = new Node[128];
            for(int i=0;i<criteria.length;i++){
            	criteria[i]=new Node(0,false);
            }
            int l=0, r=0,min=s.length()+1,todo=t.length(),minstart=0;//initialize pointer
            for(int i=0;i<t.length();i++){//initialize criteria for judge
            	criteria[t.charAt(i)].require++;
            	criteria[t.charAt(i)].isneed=true;  
            }
            
            while(r<=s.length()&&l<s.length()){//main algorithm
                if(todo>0){
                    if(r==s.length())break;
                    if(criteria[s.charAt(r)].isneed==true){
                        if(criteria[s.charAt(r)].require>0)
                            todo--;
                        criteria[s.charAt(r)].require--;
                    }
                    r++;
                }
                else{
                    if(r-l<min){
                        min=r-l;
                        minstart=l;
                    }
                    if(criteria[s.charAt(l)].isneed==true){
                        if(criteria[s.charAt(l)].require>=0)
                            todo++;
                        criteria[s.charAt(l)].require++;
                    }
                    l++;
                }
            }
            if(min == s.length()+1) return "";
            else return s.substring(minstart, minstart + min);
           // return min == s.length()+1?"":s.substring(minstart, minstart + min -1);
        }
        private class Node{
            int require;
            boolean isneed;
            public Node(int m,boolean is){
                require=m;
                isneed=is;
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.