LeetCode 76. 最小覆盖子串

2020-04-26 16:03:55来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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-滑动窗口

因为本题参数都是字母,故可以转为数组来处理;
步骤:

  1. 创建t对应的数组need并统计其字母数量为窗口参照,创建用来搜索s的窗口数组search,窗口双指针left和right从s的0位置开始,记录匹配到t中字母的计数器count和最小覆盖子串的下标记录数组min;
  2. right开始遍历s,统计到search,且若字母在need存在,则count++且最多统计need中的上限值;
  3. 当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循环语句

下一篇:Java 虚拟机中的运行时数据区分析