[LeetCode]76. Minimum Window Substring

Problem

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.

给定两个字符串S,T, 在串S中找到包含T串中所有字符的最短子串. 时间复杂度要求O(N).

时间复杂度给定了一个具体的要求.线性时间. 所以暴力破解是不可行的. 要求S的子串包含组成T的所有字符,没有顺序的要求,只要包含就行.T串字符可能会有重复元素存在. 所以使用一个unordered_map哈希表来记录T.

Solution

Analysis

具体做法,就是先记录T的组成.然后遍历S串,找到一个解之后,更新左边界,因为这个解当中可能会存在无关元素,以及重复元素.

最短: 通过一个全局变量,记录当前解的长度,及时更新这个变量,最后找到最终解.

Code

class Solution {
public:
    string minWindow(string s, string t) {
        string result = "";
        int left = 0, cnt = 0, min_len = INT_MAX;
        unordered_map<char, int> table;//t中字符可能会有重复
        
        for (auto &ch: t)
            table[ch]++;
        
        for (int i=0; i< s.size(); i++){
            if (--table[s[i]] >= 0)// s[i]是t中一个字符; 无关元素(没有出现过)会变为负数.
                cnt++;
            // 此时,这个解可能包含若干冗余元素,重复元素
            while (cnt == t.size()){//找到一个解
                if (min_len > i - left + 1){
                    min_len = i - left + 1;
                    result = s.substr(left, min_len);
                }
                if (++table[s[left]] > 0)// 更新左边界:说明left是t中一个字符,如果不是应该小于等于0
                    cnt--;
                left++;
            }
            
        }
        return result;
    }
};

References

https://www.cnblogs.com/grandyang/p/4340948.html

Problem

Solution

Analysis

Code

References

推荐文章（由hexo文章推荐插件驱动）