Minimum Window Substring 最小窗口子串问题
标签：字符串 you col 使用 imu adobe substr map rgs
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
- If there is no such window in S that covers all characters in T, return the empty string
"".
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
思路:使用到了滑动窗口，再使用Map保存目前已经匹配的目标字符串t中的元素个数。使用一个窗口(left,right)依次向右遍历。先是窗口一直向右扩张，直到(left,right)中包含目标字符串t中的所以元素的时候。
Left再向右缩，来得到最小窗口。
1 public class Minimum_Window_Substring {
2 public static String minWindow(String s, String t) {
3 if(null==s||s.length()0){
4 return "";
5 }
6
7 Map map = new HashMap();
8 int Left = 0;
9 int minLeft = 0;
10 int count = 0;
11 int minLen = s.length()+1;
12
13 for(char c:t.toCharArray()){
14 if(map.containsKey(c)){
15 map.put(c, map.get(c)+1);
16 }else{
17 map.put(c, 1);
18 }
19 }
20
21 for(int right = 0;right){
22 if(map.containsKey(s.charAt(right))){
23 map.put(s.charAt(right), map.get(s.charAt(right))-1);
24 //统计当前包含在t中的字母,如果s.charAt(right)在t中，则count++
25 if(map.get(s.charAt(right))>=0){
26 count++;
27 }
28
29 //当t中的元素都包含的时候
30 while(count==t.length()){
31 //查看当前的(Left,right)长度是否更小
32 if(right - Left +1minLen){
33 minLeft = Left;
34 minLen = right - Left +1;
35 }
36
37 //如果当前左边界包含在目标字符串t中的元素,那么则将其释放，向后遍历看是否还能匹配到更短串
38 if(map.containsKey(s.charAt(Left))){
39 map.put(s.charAt(Left), map.get(s.charAt(Left))+1);
40 if(map.get(s.charAt(Left))>0){
41 count--;
42 }
43 }
44 //缩小窗口左边界
45 Left++;
46 }
47
48 }
49 }
50
51 if(s.length()minLen){
52 return "";
53 }
54
55 return s.substring(minLeft, minLeft+minLen);
56 }
57
58 public static void main(String[] args) {
59 System.out.println(minWindow("ADOBECODEBANC","ABC"));
60 }
61 }
Minimum Window Substring 最小窗口子串问题
标签：字符串 you col 使用 imu adobe substr map rgs
原文地址：https://www.cnblogs.com/blzm742624643/p/10357757.html
评论