LeetCode-76-Minimum Window Substring

发布时间：2020-12-14 02:33:05 所属栏目：Windows 来源：网络整理

导读：算法描述： 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 c

算法描述：

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.

解题思路：子字符串问题，可以采用强大的滑动窗口方法解决。首先用map对字符串进行映射，并用两个指针分别指向窗口左边和右边，通过不断的滑动两个指针实现对窗口内字符的操作。

    string minWindow(string s,string t) {
        string res = "";
        unordered_map<char,int> map;
        for(char c:t) map[c]++;
        int left=0;
        int right = 0;
        int distance = INT_MAX;
        int count = t.size();
        int head = 0;
        while(right < s.size()){
            if(map[s[right++]]-- >0) count--;
            while(count==0){
                if(right-left< distance){
                    head = left;
                    distance = right-head;
                }
                if(map[s[left++]]++ ==0) count++;
            }
        }
        return distance==INT_MAX?"":s.substr(head,distance);
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!