leetcode hot100【Leetcode 76.最小覆盖子串】java实现
Leetcode 76.最小覆盖子串
题目描述
给你一个字符串 s 和一个字符串 t，请你在 s 中找到 t 的 最小覆盖子串。
最小覆盖子串 是指 s 中的一个子串，包含 t 中的所有字符（包括重复字符）。
返回 最小覆盖子串 的起始位置，如果没有覆盖子串，则返回空字符串 ""。
注意：
- 如果
s中没有包含t的字符，则返回""。 s和t都只包含小写字母。
示例 1：
输入：
s = "ADOBECODEBANC", t = "ABC"
输出：
"BANC"
示例 2：
输入：
s = "A", t = "A"
输出：
"A"
示例 3：
输入：
s = "A", t = "AA"
输出：
""
Java 实现代码
class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return "";
}
Map<Character, Integer> tFreq = new HashMap<>();
for (char c : t.toCharArray()) {
tFreq.put(c, tFreq.getOrDefault(c, 0) + 1);
}
int required = tFreq.size(); // 需要匹配的字符种类
int formed = 0; // 当前窗口内满足条件的字符种类
Map<Character, Integer> windowFreq = new HashMap<>();
int left = 0, right = 0; // 窗口的左右指针
int minLen = Integer.MAX_VALUE; // 最小覆盖子串的长度
int minLeft = 0; // 最小覆盖子串的起始位置
while (right < s.length()) {
char c = s.charAt(right);
windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);
// 如果当前字符的频率符合 t 中要求的频率，则增加 formed
if (tFreq.containsKey(c) && windowFreq.get(c).intValue() == tFreq.get(c).intValue()) {
formed++;
}
// 如果当前窗口内包含了 t 的所有字符，则尝试收缩窗口
while (left <= right && formed == required) {
char leftChar = s.charAt(left);
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minLeft = left;
}
// 缩小窗口，移动左指针
windowFreq.put(leftChar, windowFreq.get(leftChar) - 1);
if (tFreq.containsKey(leftChar) && windowFreq.get(leftChar).intValue() < tFreq.get(leftChar).intValue()) {
formed--;
}
left++;
}
// 移动右指针，扩大窗口
right++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}
}
解题思路
滑动窗口法：
- 本题要求我们找到
s中包含所有t中字符的最小子串，因此可以使用滑动窗口来解决。- 滑动窗口的基本思路是：我们用两个指针
left和right来维护一个窗口，该窗口内包含了t中的所有字符。
然后我们尝试缩小这个窗口，同时保证窗口内包含t中所有的字符，最终得到最小的子串。具体步骤：
- 使用哈希表记录字符串
t中各个字符的频率。- 使用两个指针
left和right来表示当前窗口的左右边界。- 当窗口中包含了
t中所有字符时，尝试收缩窗口来找到最小覆盖子串。- 当窗口不包含所有
t中的字符时，扩大窗口，直到窗口包含所有字符。优化点：
- 利用哈希表来记录字符频率，优化了对字符频率的检查。
- 在收缩窗口时，记录当前最小子串的长度和位置，最终返回最小子串。
复杂度分析
时间复杂度：
right和left指针各自最多遍历一次字符串s，因此时间复杂度为O(n)，其中n是字符串s的长度。- 哈希表操作的时间复杂度是
O(1)，因此整体时间复杂度为O(n)。空间复杂度：
- 使用了两个哈希表分别存储
t中的字符频率和当前窗口内的字符频率，最坏情况下它们的大小分别为O(m)和O(n)，其中m是t的长度，n是s的长度。- 因此空间复杂度为
O(n + m)。
原文地址：https://blog.csdn.net/qq_14815605/article/details/144107456
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！