算法:32.最小子串覆盖

https://www.lintcode.com/problem/minimum-window-substring/description

描述

给定一个字符串source和一个目标字符串target,在字符串source中找到包括所有目标字符串字母的子串。

说明

在答案的子串中的字母在目标字符串中是否需要具有相同的顺序?

——不需要。

样例

给出source = "ADOBECODEBANC",target = "ABC" 满足要求的解  "BANC"

挑战

要求时间复杂度为O(n)

思路

维护一个哈希表,以target中的字母为key。存储对象为辅助类CharInfo的对象实例,CharInfo维护一个计数器和一个队列。计数器记录了字母在target中出现的次数, 队列中存储了这个字母在source中出现的位置。在遍历source的过程中,如果当前的字母在哈希表中能够找到,那么就是target中包含的字母, 那么就需要遍历一下哈希表,如果哈希表存储的对象的队列字段的长度都大于计数器,说明目标字符串找到了,然后计算当前window的大小,Window的结束位置就是source当前字符的索引位置,window的起始位置就是哈希表中的各字母的最小位置。然后通过比较这个window的大小和已经获得的window的大小,保存较小window的起始和结束位置,最后返回。

代码

小结

题目描述中有一个地方不是很清楚,比如target如果是“AAB”,那么“AB”这个字符串是否符合要求呢?

经过测试目标中必须包含两个A。那么返回的子串长度至少等于target的长度。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180614G1UMVC00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券