Java实现 LeetCode 76 最小覆盖子串
2024-10-09 05:06:35
76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：
如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
class Solution {
//滑动窗口的应用
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
//题目里没有说只是大写 在提交的时候踩了不少坑..
int[] auxT = new int[128]; //auxT用来存目标字符串
for (int i = 0; i < t.length(); i++) {
auxT[t.charAt(i)]++;
}
int[] auxS = new int[128];//auxS用来存滑动窗口里的内容
for (int i = 0; i < t.length(); i++) {
auxS[s.charAt(i)]++;
}
//start end左右指针 min记录滑动窗口最小长度 startIndex记录最小长度的起始位置
int start = 0, end = t.length(), min = Integer.MAX_VALUE, startIndex = 0;
while (end <= s.length()) {
while (check(auxS, auxT)) {//如果包含 就移动左指针缩小范围
if (end - start < min) {
min = end - start;
startIndex = start;
}
auxS[s.charAt(start++)]--;
}
if (end <= s.length() - 1) { //这里判断一下end的越界问题
auxS[s.charAt(end++)]++;
} else {
break;
}
}
return min != Integer.MAX_VALUE ? s.substring(startIndex, startIndex + min) : "";
}
private boolean check(int[] nums1, int[] nums2) {
for (int i = 0; i < nums1.length; i++) {
if (nums1[i] < nums2[i]) {
return false;
}
}
return true;
}
}
最新文章
- Node.JS模块系统
- modelsim(2) - vcd (dump, 查看，格式理解)
- String.split使用竖线做为分隔符
- Swift 学习难点笔记
- Python 代码性能优化技巧
- [Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.3.1
- linux指令tips
- javascript有用小技巧—实现分栏显示
- Spring Mvc 用Demo去学习
- vscode 常见插件及配置 备忘
- 解决Apache配置虚拟主机时出现403错误的问题
- protobuf 编译安装
- .net like模糊查询参数化
- delphi 如何让ScrollBox的内容与滚动条一起实时滚动
- 推荐系统之隐语义模型(LFM)
- 第一次php之旅
- windows 2008R2 iis7 +php web环境安装
- Inception in CNN
- HDUOJ----2489 Minimal Ratio Tree
- [Erlang32]ibrowse流程及性能测试