Leetcode 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).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

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

题目的意思是：

　　给出两个字符串S和T，求S的最小子串（或者最小字符窗口），该子串包含所有T的字符。要求在线性时间内完成。如果没有符合要求的子串，则返回“”。如果有多个满足条件的最小子串，则返回第一个。

解题思路：

　　由于题目要求在线性时间内完成，就要减少T的字符的查找时间，故要考虑用hashMap。hashMap的查找时间复杂度是O(1)。由于目标串T可能含有重复字符，因此使用一个哈希表记录目标串的字符和字符出现的次数，同时要记录搜索窗口的已匹配的字符数count，最小字符窗口的开始位置start，已匹配的字符和次数findHashMap.

　　当已匹配的总字符数大于目标串的字符数时，即count > tLen时，要尽可能的把窗口的开始位置往后移动，即start前移，使窗口尽可能的小。

　　在移动窗口位置时必须满足的条件：

　　　（1）当前字符不在目标串T里

　　　（2）已匹配的次数大于目标串里相应字符出现的次数

注意特殊情况的处理

　　（1）两个字符串都为空的时候

　　（2）S的长度<T的长度

　　（3）S字符都不在T里面时start的处理

class Solution {

public:

    string minWindow(string S, string T) {

        if(S == "" || T == "" ||S.length() < T.length()) return "";

        int sLen =S.length(), tLen = T.length();

        unordered_map<char,int> hashMap;

        for(int i =  ; i < tLen; ++ i) hashMap[T[i]]++;

        unordered_map<char,int> findHashMap;

        int count = , start =, minLen = INT_MAX,minLenStart = -;

        for(int i =  ; i < sLen; ++ i){

            char ch = S[i];

            if(hashMap.find(ch)==hashMap.end()) continue;

            findHashMap[ch]++;

            if(findHashMap[ch] <= hashMap[ch]) count++;

            if(count>=tLen){

                char c = S[start];

                while(findHashMap.find(c) == findHashMap.end() || findHashMap[c] > hashMap[c] ){

                    if(findHashMap.find(c)!=findHashMap.end()) findHashMap[c]--;

                    start++;

                    c = S[start];

                }

                int len = i-start+;

                if(len < minLen){

                    minLen = len;

                    minLenStart = start;

                }

            }

        }

        if(minLenStart == -)return "";

        else return S.substr(minLenStart,minLen);

    }

};

巴特西

Leetcode Minimum Window Substring

最新文章

热门文章