本文主要是介绍最小覆盖子串（Leetcode76），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
例题：
分析:
比如现在有字符串（s），s = "ADOBECODEBANC", 给出目标字符串 t = "ABC", 题目就是要从原始字符串（s）中找到一个子串（res）可以覆盖目标字符串 t ，子串 "BANC"恰能覆盖 字符串t ，且长度最短，符合题目要求。
我们可以结合下图来分析：
先定义两个变量i，j，一开始，i 和 j 都指向原始字符串的0索引处，看看此时 i ~ j 范围内的字符串是否满足目标字符串（t），如果不满足，则 j 指针往后移动（j++），i 指针先不动，扩大 i ~ j 的范围，直至i ~ j 范围内的字符串满足目标字符串（t），此时记录i 和 j 的位置。 然后 j 指针不动，i++，在满足目标字符串的情况下不断缩小范围，找到最小覆盖子串。
核心思想：
1.统计目标串需要的各种字符个数，统计原始串 i ~ j 范围内各种字符个数。
2.如果原始串 i ~ j 范围内不满足条件，j++ 扩大范围，直到满足条件 j 停下来。
3.一旦满足条件 i++ 缩小范围，直到再次不满足条件。
4.重复 2、3 两步 直至 j 到达原始串末尾。
代码实现：
public class MinWindowLeetcode76 {/** 1.统计目标串需要的各种字符个数，统计原始串i~j范围内各种字符个数* 2.如果原始串i~j范围内不满足条件，j++扩大范围，直到满足条件j停下来* 3.一旦满足条件，i++缩小范围，直到再次不满足条件* 4.重复2、3两步，直至j到达原始串末尾* *///定义一个结果类，用来记录最小覆盖子串的左右边界static class Result{int i;int j;public Result(int i, int j) {this.i = i;this.j = j;}}public static String minWindow(String s, String t) {//统计目标字符串中各种字符个数char[] target = t.toCharArray();int[] targetCount = new int[128]; //因为题目说了给出的目标字符串是英文字母（大小写都有），128位足矣int passTotal = 0; //需要满足的条件，目标字符串中的一个字符代表一个条件for (char ch : target) {targetCount[ch]++;}for (int count : targetCount) {if(count > 0){passTotal++;}}//统计原始字符串i~j中各种字符个数char[] source = s.toCharArray();int[] sourceCount = new int[128];int i = 0;int j = 0;int passed = 0; //已经通过的条件个数Result res = null;while(j < source.length){//扩大 j 范围，更新范围内字符计数 和 通过条件数char right = source[j];sourceCount[right]++;if(sourceCount[right] == targetCount[right]){passed++;}//表示已经找到一个覆盖子串，缩小 i 范围，j停止，i++，同时改变通过条件数while(passed == passTotal && i <= j){if(res == null){res = new Result(i, j);}else{if(j - i < res.j - res.i){res = new Result(i, j);}}char left = source[i];sourceCount[left]--;if(sourceCount[left] < targetCount[left]){passed--;}i++;}j++;}return res == null ? "" : new String(source, res.i, res.j - res.i + 1);}public static void main(String[] args) {System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC//System.out.println(minWindow("aaabbbbbcdd", "abcdd")); // abbbbbcdd}
}
这篇关于最小覆盖子串（Leetcode76）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
