Leetcode76MinimumWindowSubstring

题意

给定一个字符串s以及字符串t，求长度最短的s的子串，该子串包含所有字符串t中的字符。

题目链接

leetcode /problems/minimum-window-substring/

题解

可利用滑动窗口求解。有两个指针l和r。l代表滑动窗口的左端点，r代表滑动窗口的右端点。用一个map保存字符串t的计数。 滑动窗口内的子串右端点不断移动，用另一个map保存这个滑动窗口内字符的计数，一旦这个滑动窗口内字符的计数包含t的计数，那么就可以移动滑动窗口的左端点，从而找到最短的子串。

class Solution { public: string minWindow(string s, string t) { int st = 0; int len = INT_MAX; int l = 0; int r = 0; unordered_map<char, int> mp; unordered_map<char, int> need; for(char c : t) { need[c]++; } int valid = 0; while( r < s.size()) { char ch = s[r]; r++; if(need.count(ch)) { mp[ch]++; if(need[ch] == mp[ch]) { valid++; } } while(valid == need.size()) { if(r - l < len) { st = l; len = r-l; } char ch = s[l]; if(need.count(ch)) { mp[ch]--; if(mp[ch] < need[ch]) { valid--; } } l++; } } return len == INT_MAX ? "" : s.substr(st,len); } };

算法复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1)