最小窗口子串

已知字符串S与字符串T,求在S中的最小窗口(区间),使得这个区间中包含 了字符串T中的所有字符。 例如: S = “ADOBECODEBANC” ;T = "ABC " 包含T的子区间中,有“ ADOBEC”, “CODEBA”, “BANC” 等等;最小窗口 区间是 “BANC” LeetCode 76. Minimum Window Substring

枚举 S = “ADOBECODEBANC” 的所有子字符串:

bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){
    for(int i = 0; i < vec_t.size(); i++){
        if(map_s[vec_t[i]] < map_t[vec_t[i]]){
            return false;
        }
    }
    return true;
}
int main(){
    std::string s= "ADOBECODEBANC";
    std::string t = "ABCDAB";
    const int MAX_ARRAY_LEN = 128;// char 0-127
    int map_t[MAX_ARRAY_LEN] = {0};//记录t字符串各字符个数
    int map_s[MAX_ARRAY_LEN] = {0};
    std::vector<int> vec_t;//记录t字符中有哪些字符
    for(int i = 0; i < s.length(); i++){
        map_s[s[i]]++;
    }
    for(int i = 0; i< t.length(); i++){
        map_t[t[i]] ++;
    }
    for(int i =0 ;i < MAX_ARRAY_LEN; i++){
        if( map_t[i] > 0){
            vec_t.push_back(i);
        }
    }
    



}

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)。

int window_begin = 0;
std::string result;
for(int i = 0; i < s.length(); i++){
    map_s[s[i]]++;
    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_s[begin_ch]){
            map_s[begin_ch]--;
            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)
        }
    }
     return result;  
    }
    
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吾爱乐享

软件测试之学习shell编程函数的使用

13540
来自专栏GopherCoder

Python 强化训练:第五篇

16930
来自专栏java学习

Java每日一练(2017/7/24)

本期题目: (单选题) 1、与InputStream流相对应的Java系统的“标准输入对象”是() A System.in B System.out C Sy...

37380
来自专栏Python

python2/3 中删除字典中value为空的键值对方法

只是在for循环中,相当于对链表的操作,它会自动调用next方法! 字典的迭代器会遍历它的键,在这个过程中,不能改变这个字典!不能删除、添加数据 要先记录要删...

25830
来自专栏菜鸟计划

javascript 变量、作用域和内存问题

一、基本类型和引用类型的值   1.基本类型和引用类型的值  基本类型值:指那些保存在栈内存中的简单数据,即这种值完全保存在内存中的一个位置,他们所占据的空间大...

38180
来自专栏Small Code

【Python】小谈numpy数组占用内存空间问题

之前跟同学讨论过numpy数组的占用空间大小问题,但是今天给忘了,又重新试验了一下,主要是利用sys模块的getsizeof函数,使用的版本是 Python3....

656100
来自专栏Android小菜鸡

JS立即执行函数的学习

格式一:(function(){})() 格式二:(funtion(){}())

17720
来自专栏用户2442861的专栏

剑指offer 33 把数组排成最小的数

转载请注明出处:http://blog.csdn.net/ns_code/article/details/28128551

13320
来自专栏pangguoming

ES6的Promise

相信凡是写过javascript的童鞋也一定都写过回调方法(callback),简单说回调方法就是将一个方法func2作为参数传入另一个方法func1中,当fu...

29830
来自专栏吴裕超

ES6之模版字符串

  但是我们可以看到:这样的传统做法需要使用大量的“”(双引号)和 + 来拼接才能得到我们需要的模版。但是这样是十分不方便的。

8510

扫码关注云+社区

领取腾讯云代金券