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

小灰灰 2022-11-10 05:26 134阅读 0赞

**[最小覆盖子串][Link 1]**

**给你一个字符串 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);
        }
    }

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

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);
        }
    }

**输出结果：**

BANC
    
    Process finished with exit code 0

**看完如果对你有帮助，感谢点赞支持！  
如果你是电脑端，看到右下角的 “一键三连” 了吗，没错点它\[哈哈\]**  
![在这里插入图片描述][20201023201048810.gif_pic_center]  
**加油！**

**共同努力！**

**Keafmd**

[Link 1]: https://leetcode-cn.com/problems/minimum-window-substring/
[20201023201048810.gif_pic_center]: /images/20221023/a34064dd34cc42fdb3c06233c6e7262c.png