Leetcode P0076"Minimum Window Substring" 题解

博文中会简要介绍Leetcode P0076题目分析及解题思路。

“Minimum Window Substring”是一道比较难但是非常经典的题目，该题充分并且完整地展示了滑动窗口思想。利用滑动窗口思路解题，需要思考如何确保窗口内的合法性，如何合理地移动左右的窗口指针，而这道题则要求解题者尽可能考虑周全。

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string “”.

If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

具体的解题思路在Java代码中已经注释，这里不再赘述。

以下是Java的题解代码实现。

class Solution {
    public String minWindow(String s, String t) {
        if (t == null || t.length() == 0)
            return "";
        
        if (s == null || s.length() == 0)
            return "";
        
        char[] tChars = t.toCharArray();
        char[] sChars = s.toCharArray();
        Map<Character, Integer> char2CountMap = new HashMap<>();
        int counter = 0;
        for (char ch: tChars) {
            char2CountMap.put(ch, char2CountMap.getOrDefault(ch, 0)+1);
            ++counter;
        }
        
        int left = 0, right = 0, count = counter, minLen = Integer.MAX_VALUE;
        int[] substrIndices = new int[] {0, 0};
        while (right < sChars.length) {
            
            while (count > 0 && right < sChars.length) {
                if (char2CountMap.containsKey(sChars[right])) {
                    char2CountMap.put(sChars[right], char2CountMap.get(sChars[right])-1);
                    // 若不是重复的，则计数器减1
                    if (char2CountMap.get(sChars[right]) >= 0)
                        --count;
                }
                
                ++right;
            }
            
            // 计数器不为零，则说明s中没有t中全部的字符
            if (count > 0)
                break;
            
            // 移动left指针，去除无关字符或者重复的有关字符
            while (left < right) {
                // 无关字符
                if (!char2CountMap.containsKey(sChars[left])) {
                    ++left;
                }
                // 重复的有关字符
                else if (char2CountMap.get(sChars[left]) < 0) {
                    char2CountMap.put(sChars[left], char2CountMap.get(sChars[left])+1);
                    ++left;
                }
                else 
                    break;
            }
            
            // 保留最小窗口
            if (right-left < minLen) {
                minLen = right-left;
                substrIndices[0] = left;
                substrIndices[1] = right;
            }
            
            // 复原HashTable和计数器并移动left指针，缩小窗口，让right指针重新寻找合法窗口
            char2CountMap.put(sChars[left], char2CountMap.get(sChars[left])+1);
            ++left;
            ++count;
        }
        
        return s.substring(substrIndices[0], substrIndices[1]);
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() == 0 || t.length() == 0)
            return "";
        
        unordered_map<char, int> char2count_map;
        int counter = 0;
        for (char ch: t) {
            ++char2count_map[ch];
            ++counter;
        }
        
        int left = 0, right = 0, count = counter, min_len = INT_MAX;
        int substr_indices[2] = {0, 0};
        while (right < s.length()) {
            while (count > 0 && right < s.length()) {
                if (char2count_map.count(s[right]) > 0) {
                    --char2count_map[s[right]];
                    if (char2count_map[s[right]] >= 0)
                        --count;
                }
                
                ++right;
            }
            
            if (count > 0)
                break;
            
            while (left < right) {
                if (char2count_map.count(s[left]) == 0)
                    ++left;
                else if (char2count_map[s[left]] < 0) {
                    ++char2count_map[s[left]];
                    ++left;
                }
                else 
                    break;
            }
            
            if (right-left < min_len) {
                min_len = right-left;
                substr_indices[0] = left;
                substr_indices[1] = right;
            }
            
            ++char2count_map[s[left]];
            ++left;
            ++count;
        }
        
        return s.substr(substr_indices[0], substr_indices[1]-substr_indices[0]);
    }
};

聖地亞歌

Leetcode P0076"Minimum Window Substring" 题解

Search

Table of Contents