[leetcode] 76. Minimum Window Substring

[leetcode] 76. Minimum Window Substring

Description

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中的所有字符，复杂度为O(n).

开始left=0，right向后移动，Tmap是T的字符计数键值对.我们用一个count来计算截取的子串是否合法，当count==T.size，说明截取的子串已经包含所给定的子串，然后我们移动left找最小的子串

代码

class Solution {public: string minWindow(string s, string t) { string result; if(!s.size()||!t.size()){ return result; } int left=0; map Tmap; for(int i=0;i0){ count++; } Tmap[s[right]]--; while(count==t.size()){ if(Tmap.find(s[left])!=Tmap.end()){ if(min_len>right-left+1){ min_len=right-left+1; result=s.substr(left,right-left+1); } Tmap[s[left]]++; if(Tmap[s[left]]>0){ count--; } } left++; } } } return result; }};

参考文献

​​[编程题]minimum-window-substring​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。