目录
一、题目描述
二、题解
一、题目描述
给定两个字符串s
和t
。返回s
中包含t
的所有字符的最短子字符串。如果s
中不存在符合条件的子字符串,则返回空字符串""
。
如果s
中存在多个符合条件的子字符串,返回任意一个。
注意:对于t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。
示例:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:”BANC”
输入:s = “a”, t = “a”
输出:”a”
二、题解
思路分析:题目要求我们找到 s 中包含 t 的所有字符的最短子字符串,即找到的子串中必须含有 t 中所有字符,可以有其他字符,返回其中最短的子串。
首先,我们很容易想到可以通过暴力枚举的方式来找到最小覆盖子串
每次记录子串的长度,并更新记录的最短子串,当i 遍历完 s 时,找到最小子串,由于当 i 找到 t 中字符时,要使用 j 向后遍历,找到子串,因此,暴力枚举的时间复杂度为O(),
当找到子串时,i 向后移动,直到再次找到 t 中字符,此时再向后寻找子串,
当再次向后寻找子串时,j可能向后移动,也可能保持不动
因此,我们可以不用每次找到 t 中字符时,都从当前下一位置向后寻找,只需从 j 上次记录的位置开始向后寻找
此时,我们可以考虑使用滑动窗口来解决本题,即使用left 和 right 两个指针维护一个窗口,窗口中不包含 t 中所有字符时,right向右滑动,添加新的字符,当窗口中包含 t 中所有字符时,判断并更新最小子串,再将left 向右滑动,移除左边元素
解题步骤:
1. 使用哈希表记录 t 中字符的种类和个数
2. 定义left 和 right 指针遍历s,并维护窗口
3. 当窗口中不含有 t 中所有字符时,向右移动 right ,添加新的字符;
当窗口中含有 t 中所有字符时,判断并更新最小子串,再向右移动 left ,直到移除t中的一个字符
再分析清楚过程后,我们可以尝试编写代码来解决本题
首先我们使用哈希表统计字符的种类和长度:
//1. //特殊情况:若s的长度小于t,直接返回空字符串if(s.length() < t.length()){return "";}//使用哈希表统计t中字符的种类和长度//由于题目中给出s和t由英文字母组成,因此我们可以使用数组模拟哈希表int[] hash1 = new int[128];//记录t中字符的种类和数量for (int i = 0; i < t.length(); i++) {hash1[t.charAt(i)]++;}
接下来我们遍历s并维护窗口:
//2. int begin = -1, minLen = -1;//记录最小子串的起始位置和长度int[] hash2 = new int[128];//记录s中字符的种类和个数//使用left和right维护窗口for (int left = 0,right = 0; right < s.length(); right++) {//右边字符进窗口char in = s.charAt(right);hash2[in]++;//判断是否需要出窗口//更新结果//左边元素出窗口}}
如何判断是否需要出窗口?
当子串包含t中所有字符时,需要出窗口。由于我们使用数组来模拟哈希表,我们可以通过遍历的方式来判断hash2中是否包含hash1中所有字符,然而,这种方式效率较低,那么我们该如何改进呢?
我们可以使用变量 count 来统计子串中有效字符(当前字符ch为 t 中字符,且此时窗口中ch的数量 小于等于 t 中 ch个数)的个数。此时,在判断出窗口时,仅需判断count 是否 大于等于 t 的长度,若大于,则出窗口
即使用count来标记子串中所含有的 t 中字符个数
注意,当前字符为 t 中字符,也可能不为有效字符,例如:
此时,虽然A为t中字符,但窗口中A的个数大于 t 中A的个数,此时的字符A不能判断为有效字符
//2.int begin = -1, minLen = -1;//记录最小子串的起始位置和长度int[] hash2 = new int[128];//记录s中字符的种类和个数//使用left和right维护窗口int count = 0;//记录窗口中有效字符的个数for (int left = 0,right = 0; right < s.length(); right++) {//右边字符进窗口char in = s.charAt(right);hash2[in]++;//判断是否是有效字符//先将字符放入哈希表后,再判断if(hash2[in] = t.length()){//更新结果if(right - left + 1 < minLen || begin == -1){begin = left;minLen = right - left + 1;}//将左边元素出窗口char out = s.charAt(left);//判断是否是有效字符出窗口//先判断当前字符是否是有效字符后,再出窗口if(hash2[out]-- <= hash1[out]){count--;}//左边元素出窗口left++;}}
最后,再返回最小覆盖子串即可
完整代码:
class Solution {public String minWindow(String s, String t) { //1.//特殊情况:若s的长度小于t,直接返回空字符串if(s.length() < t.length()){return "";}//使用哈希表统计t中字符的种类和长度//由于题目中给出s和t有英文字母组成,因此我们可以使用数组模拟哈希表int[] hash1 = new int[128];//记录t中字符的种类和数量for (int i = 0; i < t.length(); i++) {hash1[t.charAt(i)]++;}//2.int begin = -1, minLen = -1;//记录最小子串的起始位置和长度int[] hash2 = new int[128];//记录s中字符的种类和个数//使用left和right维护窗口int count = 0;//记录窗口中有效字符的个数for (int left = 0,right = 0; right < s.length(); right++) {//右边字符进窗口char in = s.charAt(right);//判断是否是有效字符//先将字符放入哈希表后,再判断if(++hash2[in] = t.length()){//更新结果if(right - left + 1 < minLen || begin == -1){begin = left;minLen = right - left + 1;}//将左边元素出窗口char out = s.charAt(left);//判断是否是有效字符出窗口//先判断当前字符是否是有效字符后,再出窗口if(hash2[out]--
题目来自:
LCR 017. 最小覆盖子串 - 力扣(LeetCode)