leetcode 76 最小窗口子串-白红宇

leetcode 76 最小窗口子串

阅读量：2434 次

发布时间：2019-05-10

本文共 2494 字，大约阅读时间需要 8 分钟。

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”

输出: “BANC”

说明：

如果 S 中不存这样的子串，则返回空字符串 “”。

如果 S 中存在这样的子串，我们保证它是唯一的答案。

算法思路：

1、设置两个字符哈希数组，map_s与map_t，map_s代表当前处理的窗口区间中的字符数量，map_t代表子串T的字符数量

2、设置两个指针(记作指针i与指针begin)指向字符串中第一个字符；

3、i指针向后逐个扫描字符串中的字符，在这个过程中，循环检查begin指针是否可以向前移动：

如果当前begin指向的字符，T中没有出现，直接前移begin
如果begin指向的字符T中出现了，但是当前区间窗口中该字符数量足够，向前移动begin，并更新map_s；
否则不能移动begin，跳出检查

4、指针i每向前扫描一个字符，即检查一下是否可以更新最终结果(找到最小的包含T中所有字符的窗口)

在整个过程中，使用begin与i维护一个窗口，该窗口中的子串满足题目条件(包含T中所有字符)，窗口线性向前滑动，整体复杂度为O(n)

begin指针的前移条件：

前进条件1：指向了没有在T中出现的字符

前进条件2：指向的字符出现在T中，但窗口内有超过T中该字符个数的字符

代码如下：

class Solution {
   public:    string minWindow(string s, string t) {
   	    int map_t[128] = {
    0 };    //记录t字符串各字符个数	    int map_s[128] = {
    0 };    //记录s字符串各字符的个数	    std::vector
   
     vec_t;    //记录t字符串中有哪些字符	    for (int i = 0; i < t.length(); i++) {
   		    map_t[t[i]]++;    	}	    for (int i = 0; i < 128; i++) {
   		    if (map_t[i] > 0) {
   			    vec_t.push_back(i);	    	}    //遍历，将字符串t中出现的字符储存到vec_t中    	}        int window_begin = 0;    //最小窗口起始指针        std::string result;    //最小窗口对应的字符串        for (int i = 0; i < s.length(); i++){
      //i代表了窗口的尾指针            map_s[s[i]]++;       //将尾指针指向的字符添加到表示窗口的map中            while (window_begin < i){
      //窗口头指针不能超过尾指针                char begin_ch = s[window_begin];                if (map_t[begin_ch] == 0){
      //如果当前头指针指向的字符没有在字符串中出现                    window_begin++;    //窗口头指针前移                }                else if (map_s[begin_ch] > map_t[begin_ch]){
                       map_s[begin_ch]--;     //头指针前移了，它指向的字符减少1                    window_begin++;    //窗口头指针前移                }                else{
                       break;                }            }            if (is_window_ok(map_s, map_t, vec_t)){
                   int new_window_len = i - window_begin + 1;                if (result == "" || result.length() > new_window_len){
       //结果字符串为空，或者当前窗口字符串更小的时候更新结果                    result = s.substr(window_begin, new_window_len);    //替换窗口对应的字符串                    //s.substr(start, length),截取一个从指定位置开始，得到指定长度的字符串                }            }        }        return result;    }private:    bool is_window_ok(int map_s[], int map_t[], std::vector
    
     & vec_t) {
   	    for (int i = 0; i < vec_t.size(); i++) {
            //利用vec_t遍历t中出现的字符	    	if (map_s[vec_t[i]] < map_t[vec_t[i]]) {
        //如果s出现该字符的数量小于t中出现该字符的数量		    	return false;		    }    	}    	return true;    }};