Java 4ms bit 97.6%


  • 17
    H

    Basically, there are two pointers for windows sliding. One for exploiting new matched substring, other pointer for expiring previous substring.

    public String minWindow(String s, String t) {
            char[] s_array = s.toCharArray();
            char[] t_array = t.toCharArray();
            int[] map = new int[256];
            int end = 0;
            int start = 0;
            int min_length = Integer.MAX_VALUE;
            for(int i = 0; i < t_array.length; i++)
                map[t_array[i]] ++;
            int count = t_array.length;
            int min_start = 0;
            while(end < s_array.length)
            {
                if(map[s_array[end]] > 0)
                {
                    count--;
                }
                map[s_array[end]] --;
                while(count == 0)
                {
                    if((end - start + 1) < min_length)
                    {
                        min_length = end - start + 1;
                        min_start = start;
                    }
                    map[s_array[start]] ++;
                    if(map[s_array[start]] > 0){
                        count ++;
                    }
                    start++;
                }
                end ++;
    
            }
            if( min_start+min_length > s_array.length)
                return "";
            return s.substring(min_start, min_start+min_length);
        }

  • 0
    V
    This post is deleted!

  • 2
    D

    Just add some comments, help u guys understand

    public String minWindow(String s, String t) {
        char[] s_array = s.toCharArray();
        char[] t_array = t.toCharArray();
        int[] map = new int[256];
        int end = 0;
        int start = 0;
        int min_length = Integer.MAX_VALUE;
        for(int i = 0; i < t_array.length; i++) // store t character and its count ----< means the lack number
            map[t_array[i]] ++;
        int count = t_array.length;
        int min_start = 0;
        
        // for those Characters t doesn't have, map[thisCharacter] are at most 0
        while(end < s_array.length)
        {
            if(map[s_array[end]] > 0)   // t has this character
            {
                count--;
            }
            map[s_array[end]] --;
            while(count == 0)   //window matches
            {
                if((end - start + 1) < min_length)
                {
                    min_length = end - start + 1;
                    min_start = start;
                }
                map[s_array[start]] ++;     // start go left
                if(map[s_array[start]] > 0){    // remove a character which t has
                    count ++;           //Cause for those Characters t doesn't have, map[thisCharacter] are at most 0
                }
                start++;
            }
            end ++;
    
        }
        if( min_start+min_length > s_array.length)
            return "";
        return s.substring(min_start, min_start+min_length);
    }

  • 1

    Had the same idea. This is my very similar implementation (3ms (98%) @ 2017-07-11 19:51:53)

    
    public class Solution {
        public String minWindow(String s, String t) {
            if (s.length() < t.length()) return "";
            int[] hash = new int[256];
            char[] chs = s.toCharArray(), cht = t.toCharArray();
            for (char c : cht) {
                hash[c]++;
            }
            int[] res = new int[2];
            int lo = 0, hi = 0, count = cht.length, minLen = Integer.MAX_VALUE;
            while (hi < chs.length) {
                char c = chs[hi];
                if (hash[c] >= 1) {
                    count--;
                }
                hash[c]--;
                hi++;
    
                while (count == 0) {
                    if (hi - lo < minLen) {
                        minLen = hi - lo;
                        res[0] = lo;
                        res[1] = hi;
                    }
                    char prev = chs[lo++];
                    if (hash[prev]++ >= 0) count++;
                }
            }
            return s.substring(res[0], res[1]);
        }
    }
    

    I avoided inlining ++ or -- except for one last place at the end, because I think this code is easier to understand. Also that I don't personally intend to perform such inlining during an actual interview.


Log in to reply
 

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