最小覆盖子串Java版（力扣）

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出："BANC"

示例 2：
输入：s = “a”, t = “a”
输出："a"

提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

题意：在字符串s中找到能覆盖字符串t的最小子串。
思路：滑动窗口。

正确代码：

class Solution { public String minWindow(String s, String t) { if(s.length()<t.length()) return ""; HashMap<Character,Integer> needs = new HashMap<>(); HashMap<Character,Integer> window = new HashMap<>(); //统计每个字符出现了多少次，以key-value的形式记录 for (int i = 0; i < t.length(); i++) { needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0)+1); } //System.out.println("needs.size(): "+needs.size()); int left =0,right=0; int valid =0; //记录多少个字符串符合了条件,valid==needs.size() 就证明全部包含了 //start : 最小符合子串的起始位置 len:最小符合子串的长度 int start =0,len =Integer.MAX_VALUE; while(right<s.length()){ char c1= s.charAt(right); if(needs.containsKey(c1)){ window.put(c1,window.getOrDefault(c1,0)+1); if(window.get(c1).equals(needs.get(c1))){ valid++; } } right++; //判断是否需要收缩 while(valid==needs.size()){ if(right-left<len){ len = right-left; start=left; } char c2 =s.charAt(left); left++; if(needs.containsKey(c2)){ window.put(c2,window.put(c2,0)-1); if(window.get(c2)<needs.get(c2)){ valid--; } } } } String a = Integer.toString(len); return a.equals(Integer.toString(Integer.MAX_VALUE) )? "" : s.substring(start, start + len); }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
 

完整代码（含测试代码）：

package com.Keafmd.February.day11;

import java.util.HashMap;

/**
 * Keafmd
 *
 * @ClassName: MinimumWindowSubstring
 * @Description: 最小覆盖子串 https://leetcode-cn.com/problems/minimum-window-substring/
 * @author: 牛哄哄的柯南
 * @Date: 2021-03-11 9:08
 * @Blog: https://keafmd.blog.csdn.net/
 */
public class MinimumWindowSubstring { public static void main(String[] args) { String s = "ADOBECODEBANC", t = "ABC"; //String s = "a", t = "aa"; //String s = "a", t = "b"; Solution03111 solution03111 = new Solution03111(); String re = solution03111.minWindow(s,t); System.out.println(re); }
}
class Solution03111 { public String minWindow(String s, String t) { if(s.length()<t.length()) return ""; HashMap<Character,Integer> needs = new HashMap<>(); HashMap<Character,Integer> window = new HashMap<>(); //统计每个字符出现了多少次，以key-value的形式记录 for (int i = 0; i < t.length(); i++) { needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0)+1); } //System.out.println("needs.size(): "+needs.size()); int left =0,right=0; int valid =0; //记录多少个字符串符合了条件,valid==needs.size() 就证明全部包含了 //start : 最小符合子串的起始位置 len:最小符合子串的长度 int start =0,len =Integer.MAX_VALUE; while(right<s.length()){ char c1= s.charAt(right); if(needs.containsKey(c1)){ window.put(c1,window.getOrDefault(c1,0)+1); if(window.get(c1).equals(needs.get(c1))){ valid++; } } right++; //判断是否需要收缩 while(valid==needs.size()){ if(right-left<len){ len = right-left; start=left; } char c2 =s.charAt(left); left++; if(needs.containsKey(c2)){ window.put(c2,window.put(c2,0)-1); if(window.get(c2)<needs.get(c2)){ valid--; } } } } String a = Integer.toString(len); return a.equals(Integer.toString(Integer.MAX_VALUE) )? "" : s.substring(start, start + len); }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
 

输出结果：

BANC

Process finished with exit code 0

  

 

  
1
  
2
  
3
 

看完如果对你有帮助，感谢点赞支持！
如果你是电脑端，看到右下角的 “一键三连” 了吗，没错点它[哈哈]

加油！

共同努力！

Keafmd

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/114879844