美文网首页
76 minimum Window Substring(two

76 minimum Window Substring(two

作者: Fei_JOB | 来源:发表于2017-10-23 11:06 被阅读0次
import java.io.*;
import java.util.*;

class myCode
{
     public String minWindow( String s, String t ){
         
        if(t.length() > s.length()) return "";
         
         int[] hash = new int[26];
         int match = 0;
         int start = 0;
         int min = Integer.MAX_VALUE;
         int left = 0;
         
         for(char c: t.toCharArray()){
             hash[c-'A']++;
             if(hash[c-'A'] == 1) match++;
         }
         
         for(int end = 0; end < s.length(); end++ ){
             char e = s.charAt(end);
             hash[e-'A']--;
             if(hash[e-'A'] == 0) match--;
             while(match == 0){
                 if(min > end - start + 1){
                     min = end - start + 1;
                     left = start;
                 }
                 char st = s.charAt(start++);
                 hash[st-'A']++;
                 if(hash[st-'A'] == 1) match++;
             }
             
         }
         if(min == Integer.MAX_VALUE) return "";
         return s.substring(left, left + min);
     }
    
    public static void main (String[] args) throws java.lang.Exception
     {
        myCode test = new myCode();
        System.out.println(test.minWindow("ABDOBECODEBANC", "ABC"));
        
    }
}

相关文章

网友评论

      本文标题:76 minimum Window Substring(two

      本文链接:https://www.haomeiwen.com/subject/ajwouxtx.html