JAVA练习280- 最小覆盖子串

题目概览

给定两个字符串s和t，长度分别是m和n，返回 s 中的最短窗口 子串，使得该子串包含t中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串""。

测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"输出："a"解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入:s = "a", t = "aa"输出:""解释:t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s和t由英文字母组成

来源：76. 最小覆盖子串 - 力扣（LeetCode）

解题分析

方法：滑动窗口

求最小子串其实就是看每个满足条件的滑动窗口长度最小，我们可以定义 i 和 j 一同指向第一个元素，当 i 和 j 范围内元素不满足条件，往右边移动；若满足条件，则得到一个初步的子串，由于 i 指向的元素不能不在 t 中，因此还要移动 i 直到不满足条件，这样就可以得到一个可能是最小的子串。然后继续移动 j，重复步骤即可。

看是否满足条件可以定义一个哈希map来存储 t 的字母和出现次数，然后比较当前子串字母和次数是否对的上即可。由于这里的字母都是大小写英文字母，我们也可以用 128 的数组来实现。

时间复杂度：O(n)
空间复杂度：O(k)

class Solution { public String minWindow(String s, String t) { int[] mapping = new int[128]; char[] cs = s.toCharArray(); char[] ct = t.toCharArray(); for (char c: ct) { mapping[c]++; } int tLen = ct.length, sLen = cs.length; int i = 0, j = 0; int[] temp = new int[128]; int minI = 0, minJ = sLen; while(i < sLen && j < sLen) { temp[cs[j]]++; while(isCovered(temp, mapping)) { if (j - i < minJ - minI) { minI = i; minJ = j; } temp[cs[i]]--; i++; } j++; } return minJ == sLen ? "" : s.substring(minI, minJ + 1); } public boolean isCovered(int[] cs, int[] ct) { for (int i = 'A'; i <= 'Z'; i++) { if (cs[i] < ct[i]) { return false; } } for (int i = 'a'; i <= 'z'; i++) { if (cs[i] < ct[i]) { return false; } } return true; } }