Share my neat java solution


  • 37
    T
    public String minWindow(String S, String T) {
        if(S==null||S.isEmpty()||T==null||T.isEmpty()) return "";
        int i=0, j=0;
        int[] Tmap=new int[256];
        int[] Smap=new int[256];
        for(int k=0; k< T.length(); k++){
            Tmap[T.charAt(k)]++;
        }
        int found=0;
        int length=Integer.MAX_VALUE;
        String res="";
        while(j<S.length()){
            if(found<T.length()){
                if(Tmap[S.charAt(j)]>0){
                    Smap[S.charAt(j)]++;
                    if(Smap[S.charAt(j)]<=Tmap[S.charAt(j)]){
                        found++;
                    }
                }
                j++;
            }
            while(found==T.length()){
                if(j-i<length){
                    length=j-i; res=S.substring(i,j);
                }
                if(Tmap[S.charAt(i)]>0){
                    Smap[S.charAt(i)]--;
                    if(Smap[S.charAt(i)]<Tmap[S.charAt(i)]){
                        found--;
                    }
                }
                i++;
            }
        }
        return res;
    }

  • 0
    R

    what is the complexity?


  • 10

    Using count.
    题意是找到str中最短的substring,它里面与t的所有字母对应的数量更多。
    比如t里面有3个A,那么substring里面至少有3个A。
    第一步,数一下t里面每个字母出现了多少次。
    第二步,move end point,找到str中满足条件的字符串。就是刚好减掉了n个,n是t的长度。
    第三步,move start point,去夹逼最小的substring,意思就是move start到不能往右移为止,多移一位substring就不满足条件。
    第四步,比较长度。
    第五步,把start右移一位,让substring不满足条件。
    回到第二步。

      public String minWindow(String str, String t) {
          int[] map = new int[256];
          for(char c: t.toCharArray()){
            map[c - 'A']++;
          }
          
          int minLen = Integer.MAX_VALUE, minStart = 0;
      
          int n = t.length();
          char[] sc = str.toCharArray();
          int s = 0, e = 0;
          while(e < sc.length){
            int ie = sc[e] - 'A';
            map[ie]--;
            if(map[ie] >= 0){
              n--; 
            }
            
            if(n == 0){
              int is = sc[s] - 'A';
              while(map[is] < 0){
                map[is]++;
                s++;
                is = sc[s] - 'A';  
              }
              
              int len = e - s + 1;
              if(len < minLen){
                minLen = len;
                minStart = s;
              }
              
              map[is]++;
              s++;
              n++;
            }
            e++;
          }
      
          return minLen == Integer.MAX_VALUE ? "" : str.substring(minStart, minStart + minLen);
        }
    

    Using HashMap.
    alt text


  • 0

    @rabeeh O(n)


  • 0
    R
    This post is deleted!

  • 0
    K

    @Jerry Awesome Thanks a lot for that. Saved my day :)


  • 0
    X

    @Jerry 跟我想的一样。赞一个。


Log in to reply
 

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