美文网首页
* 76. Minimum Window Substring -

* 76. Minimum Window Substring -

作者: 沉睡至夏 | 来源:发表于2016-10-21 07:10 被阅读171次

    解题思路:

    1. 利用Array的index存两个string的词频。
    2. 什么情况下找到一个valid的字符;
    3. 什么情况下找到一个valid的完整字符串;

    当找到这个字符串的时候:

    1. 跳过前面多余的字符;
    2. 更新需求,即最短长度;若更新了,记录开头和结尾;
    3. 跳过这个字符串的首字符,继续扫(found也要减一)。

    ====
    看到题的第一反应,先数S中每个字母有多少个,以后后面一定要一个一个减掉。
    我最初的想法:
    s = “DADOBECODEBANC”
    t = “ABC“
    okay, scan S, start from the letter that also appears in T. here, we start from ADOBEC. this is an possible answer。
    Then we skip the first A (cnt A--), start from B, BECODEBA. But when we arrives B, which locates between E and A, we skip the first B (cnt B --), since it will definitely gives shorter answer. keep working till the end.
    因为先要存t的字频,之后查表,所以一定会用到hashTable/hashMap;

    看了答案,答案用了hash的思想,但是只用array就存储了cnt的信息。

    public class Solution {
        public String minWindow(String s, String t) {
            int[] sCnt = new int[255];
            int[] tCnt = new int[255];
            
            for (int i=0; i<t.length(); i++) {
                tCnt[t.charAt(i)]++;
            }
            
            int start = 0;
            int begin = -1, end = s.length();
            int found = 0, minLen = s.length();
            
            for (int i=0; i<s.length(); i++) {
                char c1 = s.charAt(i);
                sCnt[c1]++;
                if(sCnt[c1] <= tCnt[c1])    found++;
                if(found == t.length()) {
                    while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
                        sCnt[s.charAt(start)]--;
                        start++;
                    }
                    
                    if(i-start < minLen) {
                        minLen = i-start;
                        begin = start;
                        end = i;
                    }
                    
                    sCnt[s.charAt(start)]--;
                    start++;
                    found--;
                }
            }
            return begin == -1 ? "" : s.substring(begin, end+1);
        }
    }
    

    总结一下:直接在代码里写吧。

    public class Solution {
        public String minWindow(String s, String t) {
            int[] sCnt = new int[255];
            int[] tCnt = new int[255];
            
            for (int i=0; i<t.length(); i++) {
                tCnt[t.charAt(i)]++;
            }
            
            int start = 0;
            int begin = -1, end = s.length();
            int found = 0, minLen = s.length();
            
            for (int i=0; i<s.length(); i++) {
                char c1 = s.charAt(i);
                sCnt[c1]++;
                /** 如果算上这个字符后,数量不超过t中这个字符的数量,那么这个字符算是valid(即找到一个匹配的字符);
                 */
                if(sCnt[c1] <= tCnt[c1])    found++;
                /** 找到一个valid的字符串。
                 */
                if(found == t.length()) {
                    /** 这个字符串end一定是i。现在需要找到这个字符串的起始位置。
                     * 起始位置那个字符在s中出现的次数一定和在t中出现的次数一样多;
                     * 所有那些s中出现次数比t中多的,一定是多余的,从前往后扫,然后全部删掉。
                     * 记得每次从s中散掉的时候,s对这个字符的cnt也要减一。
                     */ 
                    while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
                        sCnt[s.charAt(start)]--;
                        start++;
                    }
                    /** 更新minLen,如果更新了,那么记录下这个长度的起始点和终点。 
                     */
                    if(i-start < minLen) {
                        minLen = i-start;
                        begin = start;
                        end = i;
                    }
                    
                    /** 把开头的start跳过,注意sCnt也要减一,继续扫。
                     */ 
                    sCnt[s.charAt(start)]--;
                    start++;
                    found--;
                }
            }
            return begin == -1 ? "" : s.substring(begin, end+1);
        }
    }
    

    相关文章

      网友评论

          本文标题:* 76. Minimum Window Substring -

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