LeetCode 76. 最小覆盖子串
2020-04-26 16:03:55来源:博客园 阅读 ()
LeetCode 76. 最小覆盖子串
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 76. 最小覆盖子串
题目
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明:
- 如果 S 中不存这样的子串,则返回空字符串 ""。
- 如果 S 中存在这样的子串,我们保证它是唯一的答案。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
很自然能想到的是用滑动窗口来解决;
题目有个坑就是,对于s="aaa"和t="aa",答案是"aa"而不是"a",就是说,子串必须包含t的所有字母数量至少是t的长度;
思路1-滑动窗口
因为本题参数都是字母,故可以转为数组来处理;
步骤:
- 创建t对应的数组need并统计其字母数量为窗口参照,创建用来搜索s的窗口数组search,窗口双指针left和right从s的0位置开始,记录匹配到t中字母的计数器count和最小覆盖子串的下标记录数组min;
- right开始遍历s,统计到search,且若字母在need存在,则count++且最多统计need中的上限值;
- 当count等于t的长度时表明找到了一个覆盖子串,此时停止right,从left开始缩小窗口,若找到了更小的坐标则更新min;
算法复杂度: n1为s的长度,n2为t的长度
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n1+n2\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $
算法源码示例
package leetcode;
import java.util.HashMap;
/**
* @author ZhouJie
* @date 2020年3月6日 下午9:41:21
* @Description: 76. 最小覆盖子串
*
*/
public class LeetCode_0076 {
}
class Solution_0076 {
/**
* @author: ZhouJie
* @date: 2020年3月6日 下午11:46:51
* @param: @param s
* @param: @param t
* @param: @return
* @return: String
* @Description: 2-按照题意要求,将1的改造一下,hash哈希表存对应字符出现次数;
* cache改为map类型,思路不变,但是改为校验cache的map与has是否完全一致即可;
*
* 因为题目中的都是字母,所以不用HashMap改用128长度的数组足矣,
*
*/
public String minWindow_2(String s, String t) {
int tLen = 0, sLen = 0;
// 特例判断
if (t == null || (tLen = t.length()) == 0) {
return "";
}
// 特例判断
if (s == null || (sLen = s.length()) < tLen) {
return "";
}
// 需要找到的字母和数量,转为数组记录
int[] need = new int[128];
for (char c : t.toCharArray()) {
need[c]++;
}
// 滑动窗口中的字母和数量
int[] search = new int[128];
// 滑动窗口左右指针和统计匹配到t中字母的计数count
int left = 0, right = 0, count = 0;
int[] min = new int[] { 0, sLen };
while (right < sLen) {
char c = s.charAt(right);
// 记录s中当前字母数量,若是need中要找的,则count++且最多加need中的上限个
search[c]++;
if (need[c] > 0 && need[c] >= search[c]) {
count++;
}
// 若s中的字母在t中全找到了,则开始从左侧缩小窗口
while (count == tLen) {
c = s.charAt(left);
if (need[c] > 0 && need[c] >= search[c]) {
count--;
}
// 若找到了更小的窗口则更新
if (right - left < min[1] - min[0]) {
min[0] = left;
min[1] = right;
}
search[c]--;
left++;
}
right++;
}
// 需要验证min[1],未找到时返回"",否则截取s返回,记得截取右侧位置要+1
return min[1] == sLen ? "" : s.substring(min[0], min[1] + 1);
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12781194.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:while循环语句
- LeetCode 287. 寻找重复数 2020-05-31
- 数组小Demo 2020-05-25
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash