今天我们看一道 leetcode hard 难度题目:最小覆盖子串。
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
对于 t
中重复字符,我们寻找的子字符串中该字符数量必须不少于 t
中该字符数量。 如果 s
中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
最容易想到的思路是,s 从下标 0~n 形成的子串逐个判断是否满足条件,如:
ADOBEC..
DOBECO..
OBECOD..
因为最小覆盖子串是连续的,所以该方法可以保证遍历到所有满足条件的子串。代码如下:
function minWindow(s: string, t: string): string {
// t 剩余匹配总长度
let tLeftSize = t.length
// t 每个字母对应出现次数表
const tCharCountMap = {}
for (const char of t) {
if (!tCharCountMap[char]) {
tCharCountMap[char] = 0
}
tCharCountMap[char]++
}
let globalResult = ''
for (let i = 0; i < s.length; i++) {
let currentResult = ''
let currentTLeftSize = tLeftSize
const currentTCharCountMap = { ...tCharCountMap }
// 找到以 i 下标开头,满足条件的字符串
for (let j = i; j < s.length; j++) {
currentResult += s[j]
// 如果这一项在 t 中存在,则减 1
if (currentTCharCountMap[s[j]] !== undefined && currentTCharCountMap[s[j]] !== 0) {
currentTCharCountMap[s[j]]--
currentTLeftSize--
}
// 匹配完了
if (currentTLeftSize === 0) {
if (globalResult === '') {
globalResult = currentResult
} else if (currentResult.length < globalResult.length) {
globalResult = currentResult
}
break
}
}
}
return globalResult
};
我们用 tCharCountMap
存储 t
中每个字符出现的次数,在遍历时每次找到出现过的字符就减去 1,直到 tLeftSize
变成 0,表示 s
完全覆盖了 t
。
这个方法因为执行了 n + n-1 + n-2 + ... + 1 次,所以时间复杂度是 O(n²),无法 AC,因此我们要寻找更快捷的方案。
追求性能的降级方案是滑动窗口或动态规划,该题目计算的是字符串,不适合用动态规划。
那滑动窗口是否合适呢?
该题要计算的是满足条件的子串,该子串肯定是连续的,滑动窗口在连续子串匹配问题上是不会遗漏结果的,所以肯定可以用这个方案。
思路也很容易想,即:如果当前字符串覆盖 t
,左指针右移,否则右指针右移。就像一个窗口扫描是否满足条件,需要右指针右移判断是否满足条件,满足条件后不一定是最优的,需要左指针继续右移找寻其他答案。
这里有一个难点是如何高效判断当前窗口内字符串是否覆盖 t
,有三种想法:
第一种想法是对每个字符做一个计数器,再做一个总计数器,每当匹配到一个字符,当前字符计数器与总计数器 +1,这样直接用总计数器就能判断了。但这个方法有个漏洞,即总计数器没有包含字符类型,比如连续匹配 100 个 b
,总计数器都 +1,此时其实缺的是 c
,那么当 c
匹配到了之后,总计数器的值并不能判定出覆盖了。
第一种方法的优化版本可能是二进制,比如用 26 个 01 表示,但可惜每个字符出现的次数会超过 1,并不是布尔类型,所以用这种方式取巧也不行。
第二种方法是笨方法,每次递归时都判断下 s 字符串当前每个字符收集的数量是否超过 t 字符串每个字符出现的数量,坏处是每次递归都至多多循环 25 次。
笔者想到的第三种方法是,还是需要一个计数器,但这个计数器 notCoverChar
是一个 Set<string>
类型,记录了每个 char 是否未 ready,所谓 ready 即该 char 在当前窗口内出现的次数 >= 该 char 在 t
字符串中出现的次数。同时还需要有 sCharMap
、tCharMap
来记录两个字符串每个字符出现的次数,当右指针右移时,sCharMap
对应 char
计数增加,如果该 char
出现次数超过 t
该 char
出现次数,就从 notCoverChar
中移除;当左指针右移时,sCharMap
对应 char
计数减少,如果该 char
出现次数低于 t
该 char
出现次数,该 char
重新放到 notCoverChar
中。
代码如下:
function minWindow(s: string, t: string): string {
// s 每个字母出现次数表
const sCharMap = {}
// t 每个字母对应出现次数表
const tCharMap = {}
// 未覆盖的字符有哪些
const notCoverChar = new Set<string>()
// 计算各字符在 t 出现次数
for (const char of t) {
if (!tCharMap[char]) {
tCharMap[char] = 0
}
tCharMap[char]++
notCoverChar.add(char)
}
let leftIndex = 0
let rightIndex = -1
let result = ''
let currentStr = ''
// leftIndex | rightIndex 超限才会停止
while (leftIndex < s.length && rightIndex < s.length) {
// 未覆盖的条件:notCoverChar 长度 > 0
if (notCoverChar.size > 0) {
// 此时窗口没有 cover t,rightIndex 右移寻找
rightIndex++
const nextChar = s[rightIndex]
currentStr += nextChar
if (sCharMap[nextChar] === undefined) {
sCharMap[nextChar] = 0
}
sCharMap[nextChar]++
// 如果 tCharMap 有这个 nextChar, 且已收集数量超过 t 中数量,此 char ready
if (
tCharMap[nextChar] !== undefined &&
sCharMap[nextChar] >= tCharMap[nextChar]
) {
notCoverChar.delete(nextChar)
}
} else {
// 此时窗口正好 cover t,记录最短结果
if (result === '') {
result = currentStr
} else if (currentStr.length < result.length) {
result = currentStr
}
// leftIndex 即将右移,将 sCharMap 中对应 char 数量减 1
const previousChar = s[leftIndex]
sCharMap[previousChar]--
// 如果 previousChar 在 sCharMap 数量少于 tCharMap 数量,则不能 cover
if (sCharMap[previousChar] < tCharMap[previousChar]) {
notCoverChar.add(previousChar)
}
// leftIndex 右移
leftIndex++
currentStr = currentStr.slice(1, currentStr.length)
}
}
return result
};
其中还用了一些小缓存,比如 currentStr
记录当前窗口内字符串,这样当可以覆盖 t
时,随时可以拿到当前字符串,而不需要根据左右指针重新遍历。
该题首先要排除动态规划,并根据连续子串特性第一时间想到滑动窗口可以覆盖到所有可能性。
滑动窗口方案想到后,需要想到如何高性能判断当前窗口内字符串可以覆盖 t
,notCoverChar
就是一种不错的思路。
讨论地址是:精读《算法 - 最小覆盖子串》· Issue #496 · dt-fe/weekly
如果你想参与讨论,请 点击这里,每周都有新的主题,周末或周一发布。前端精读 - 帮你筛选靠谱的内容。
版权声明:自由转载-非商用-非衍生-保持署名(创意共享 3.0 许可证)
文章浏览阅读3.1k次。错误原因是出现导入的第三方库中的包和 现有的包版本冲突 或者重复解决如下删除重复的包在gradle中排除版本冲突 exclude module 冲突的包 api ("com.alibaba:arouter-api:$rootProject.arouterVersion") { exclude module: 'support-v4' }..._android dependency 'com.android.support:support-v4' has different version fo
文章浏览阅读2.9k次,点赞13次,收藏121次。#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status;typedef int ElemType;//单链表的存储结构typedef struct LNode{ ElemType data; struct LNode *next; //next指向自身类型struct LNode *的指_设立尾指针的单循环链表的十二个基本操作c语言要有菜单
文章浏览阅读467次。1.包含头文件2.编译时命令使用gcc -o xthread xthead.c -lpthread或者 gcc -lphread xthread.c -o xthread
文章浏览阅读128次。linux是什么系统_网站服务器运行维护Linuxjavascript:;,全称GNU/Linux,是一套免费使用和自由传播的类UNIX操作系统,它主要受到Minix和Unix思想的启发,是一个基于POSIX和Unix的多用户、多任务、支持多线程和多CPU的操作系统。Ubuntu中怎么使用apt-get安装指定php版本号命令用法如下:sudo apt-get install package=ve...
文章浏览阅读4.3k次。遇到自己创建的.h头文件被识别出无法添加源文件,找了很多教程看了很多文章,都不管用,最后在includepath中的每一条路径里面最后面加上\**,就成功解决了这个问题
文章浏览阅读128次。 我是《C程序设计伴侣》的策划编辑,有话在这里说。(一) 作者 人民邮电出版社图灵公司副总编 陈冰 【背景介绍: 2012年7月27日,人民邮电出版社图灵公司对外透露,将在今年8、9月出版所谓的“图灵原创”《C程序设计伴侣》(后面简称《伴侣》)。(http://photo.weibo.com/1847982423/talbum/detail/photo_id/347234610044..._站在巨人的肩膀上跪在巨人脚下
文章浏览阅读742次,点赞2次,收藏2次。显错注入显错注入是SQL注入的一种,而SQL注入是指web应用程序对用户输入数据的合法性没有判断,导致攻击者可以构造不同的sql语句来实现对数据库的操作。SQL注入漏洞产生的条件: 1、用户能够控制数据的输入。 2、原本执行需要执行的代码时,拼接了用户的输入。打开webug靶场,打开id为1的靶场后,如图:这里我们使用工具的是Hackbar2.1.3版本,这个是免费的。首先,我们需要判断是否存在SQL注入。在参数后面多加一个单引号,然后将它上传,发现报错了通过页面的返回结果,_webug靶场
文章浏览阅读3.5w次,点赞23次,收藏139次。环境介绍Active Directory域控制器已经搭建好主域控和辅域控,主域控故障,手动升级辅域控为主。主域控:2012DC1,ip:192.168.15.1辅域控:2012DC2,ip:192.168.15.21、升级前分别在2012dc1和2012dc2上查询fsmo的归属2、在2012dc1上,打开AD用户和计算机,更改连接的域控制器3、选择20..._升级域控
文章浏览阅读1k次,点赞3次,收藏4次。很多人搞不懂springboot和spring-cloud的关系到底是什么,也不知道这两者时间有什么区别,今天简单的聊聊。2022年发了一篇Springcloud和Springboot的区别对比,但后面回看总觉得少了点东西,这次重新发个补充一下。_spring cloud 源码
文章浏览阅读1.2w次,点赞2次,收藏5次。关于这类问题一般有两种场景引用第三方组价时,比如引用vue-awesome-swiper这种的第三方组件时,因为源组件代码中包含有操作window对象,所以这一类的window is not defined按照官方的使用插件的方法引入就可以解决// 这里就以vue-awesome-swiper这个组件为例import Vue from 'vue'import VueAwesomeSwi...
文章浏览阅读1.2k次。如何正确理解配置管理 在实际项目工作中,我们能回答项目组中不同角色人员提出的问题吗? 项目经理:还有没有重要性为1的请求没有解决? 分析设计人员:这次发布版本是否包括了462需求? 开发人员:我记得的确修改了那个文件的,为什么还会出现这个问题? 集成人员:为什么这次build失败了? 测试人员:Bug 873是否在这次build中fix了? …… 实际情况是,我们很难_配置项管理和受控状态解释
文章浏览阅读38次。因为"%Y年%m月%d日%H时%M分%S秒" 并不会使文字显现在屏幕上 t.write('年',font=('Arial',25,'normal')等才能write文字。通过代码的编写输出从电脑获取的本地时间包括年月日。设置画布画笔的参数将中文年月日通过。代码运行后可以成功显示数字0-9。根据数码管的明暗条件编写程序。