Java version if you have trouble reading highest uprated post. 中文版


  • 1
    B

    我觉得这题的精髓在于记录字符出现字数的Map可以记录负数,也就是说某个字符被过多用了,之前本人也是没想到能记录负数, 所以感觉s=“bba” t="ab" 这种情况不知如何解。我想大家应该对双指针这种解法应该没有什么问题。请看代码:

    The key for this problem should be tracking how every char is used in t. In particular, everytime when a char is used, we do map[end_ch]--. If map[end_ch] becomes negative, this means the char is over used. And when moving the left pointer right, we should increase map[start_ch]++ until we find map[start_ch] is positive. If we don't record if a char is overused, we cannot solve cases like s = "bba", t = "ab".

        public String minWindow(String s, String t) {
            if (s == null || t == null) return "";
            int[] map = new int[256];
            for (char c : t.toCharArray()) map[c]++;
            
            int start = 0, remainingChar = t.length();
            int minLen = Integer.MAX_VALUE,  minLenStartIdx = 0;
            for (int end = 0; end < s.length(); end++) {
                char end_ch = s.charAt(end);
                
                if (map[end_ch] > 0) remainingChar--;//若这个字符有余额,使用以后需要减减我们剩余可用字符的数量:remainingChar
                map[end_ch]--;//碰到任意字符,使用过就要减减
                
                while (remainingChar == 0 && start < s.length()) {
                    if (minLen > end-start+1) {//找到比目前的更优解,记录之
                        minLen = end-start+1;
                        minLenStartIdx = start;
                    }
                    
                    char start_ch = s.charAt(start);
                    map[start_ch]++;
                    if ( map[start_ch] > 0) remainingChar++;//这里关键,start指的字符已经被加加,如果这时候还不大于0,说明这个字符被过多使用了,remainingChar就不能增加
                    start++;
                }
            }
            
            return minLen == Integer.MAX_VALUE ? "" : s.substring(minLenStartIdx, minLenStartIdx+minLen);
        }
    

Log in to reply
 

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