Minimum Window Substring

这道string的题目还比较复杂,其算法解释在

用两个指针first 和 last,先last开始找到一个合法的包含所有子数的window,然后first再向后step找到最小的window,然后再继续。需要注意的是用两个hashmap来记录访问过的char的数目,这样来处理有相同字母的情况,一个是needed,另一个是found,needed是T中各个字母出现的个数。

首先last开始向右step直到找到一个legal的window,我们用一个count来计算,当遇到一个neede的字母并且found里的数还小于needed中字母的数的时候,count++,如果超过了则不计入count内,当count == T.length的时候,第一个legal的window就找到了,这个比较巧妙。
然后first向右step,检查每个字母是否再needed中,如果不在,或者即使在,但他在found中的值大于needed值,那么first可以向右移动(相当于这个可以从window里删除出去而window还是合法的)

这样一直下去直到last == S.length即可。

public class Solution {
    public String minWindow(String S, String T) {
        //store no of chars in the T to hashMap t, for duplicate chars
        HashMap<Character, Integer> needed = new HashMap<Character, Integer>();
        HashMap<Character, Integer> found = new HashMap<Character, Integer>();
        for (int i = 0; i < T.length(); i++)
        {
            if (needed.containsKey(T.charAt(i)))
                needed.put(T.charAt(i), needed.get(T.charAt(i)) + 1);
            else
            {
                needed.put(T.charAt(i), 1); //init needed and found
                found.put(T.charAt(i), 0);
            }
        }
        //find first legal window, mark with first and last
        int minFirst = -1;
        int minLast = S.length() - 1;
        int min = S.length();
        int first = 0;
        int last = 0;
        int count = 0; // track if the first elegable window is found
        for (first = 0, last = 0; last != S.length(); last++) // use last to scan the whole string S
        {
            char curr = S.charAt(last);
            if (needed.containsKey(curr))
            {
                found.put(curr, found.get(curr) + 1);
                if (found.get(curr) <= needed.get(curr)) // if it is not an extra, count ++ ,when count == T.length(),first window is found
                    count++;
            }
            
            if (count == T.length()) // first window is found
            {
                char f = S.charAt(first); //move first until it makes an illegle window.
                while(!needed.containsKey(f) || found.get(f) > needed.get(f))
                {
                    if (found.containsKey(f))
                        found.put(f, found.get(f) - 1);
                    first++;
                    f = S.charAt(first);
                }
                if (min >= last - first + 1)
                {
                    minFirst = first;
                    minLast = last;
                    min = last - first + 1;
                }
            }
        }
        return minFirst == -1? "" : S.substring(minFirst, minLast + 1);
    }
}

Second Submission:

Use a count variable to check if the whole string has been found or not. Then move the head and tail pointer in turn to get the final result. tail keeps moving to the end, and every time increase the tail pointer, try to move the begin pointer to Keep count = T.length until the end of the program.

public class Solution {
    public String minWindow(String S, String T) {
        // init bench
        HashMap<Character, Integer> bench = new HashMap<Character, Integer>();
        for (int i = 0; i < T.length(); i++) {
            if(!bench.containsKey(T.charAt(i))) {
                bench.put(T.charAt(i), 1);
            } else {
                bench.put(T.charAt(i), bench.get(T.charAt(i)) + 1);
            }
        }
        HashMap<Character, Integer> filled = new HashMap<Character, Integer>();
        HashMap<Character, Integer> first = new HashMap<Character, Integer>(bench);
        // find first
        int head = 0;
        int tail = 0;
        int count = 0; //count to decide if the window length is met or not !!!
        int len = S.length();
        String result = "";
        boolean found = false;
        while(tail < S.length()) {
            char c = S.charAt(tail);
            if (bench.containsKey(c)) {
                if (!filled.containsKey(c)) {
                    filled.put(c, 1);
                    count++;
                } 
                else {
                    if (filled.get(c) < bench.get(c))
                        count++;
                    filled.put(c, filled.get(c) + 1);
                }
            }
            if (count == T.length()) {// very efficient way to check if the window is met or not
                char d = S.charAt(head);
                while (!filled.containsKey(d) ||(filled.containsKey(d) && filled.get(d) > bench.get(d))) {
                    if (filled.containsKey(d) && filled.get(d) > bench.get(d))
                        filled.put(d, filled.get(d) - 1);
                    head++;
                    d = S.charAt(head);
                }
                if (tail - head + 1 <= len) {
                    len = tail - head + 1;
                    result = S.substring(head, tail + 1);
                }
            }
            tail++;  
        }
        return result;
    }
}

Although we can do i + len when running the matching, we still need to test every i during the scan on S. Also we can stop when we hit T.length() – S.length().

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        if (L.length == 0)
            return res;
        int len = L[0].length();
        int totalLen = 0;
        for (int i = 0; i < L.length; i++) {
            String s = L[i];
            if (map.containsKey(s)) {
                map.put(s, map.get(s)+1);
            }
            else {
                map.put(s, 1);
            }
            totalLen += len;
        }
        
        for (int i = 0; i <= S.length() - totalLen; i++) {
            HashMap<String, Integer> tmp = new HashMap<String, Integer>();
            int j = i;
            while(j < i + totalLen) {
                String s = S.substring(j, j+len);
                if (map.containsKey(s)) {
                    if (!tmp.containsKey(s)) {
                        tmp.put(s, 1);
                        j += len;
                    }
                    else {
                        if (tmp.get(s) < map.get(s)) {
                            tmp.put(s, tmp.get(s) + 1);
                            j += len;
                        } 
                        else {
                            break;
                        }
                    }
                }
                else {
                    break;
                }
            }
            if (j == i + totalLen) {
                res.add(i);
            }
        }
        return res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s