最小覆盖子串

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"

输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路：采用滑动窗口，窗口有左右边界，先通过扩展右边界找出一个包含T中所有字符的子串，然后收缩左边界，直到不能再收缩。记录此时的子串。然后收缩左边界，继续扩展右边界，直到再找到满足要求的子串，和上次的进行比较，保存更小的子串。返回执行，直到右边界到达S串尾，且左边界不能再收缩。

 import java.util.*;

 public class Solution {

     public static String minWindow(String s,String t){

         Map<Character,Integer> map=new HashMap<>();

         int min=Integer.MAX_VALUE;

         int minStart=0,minEnd=0;

         int count=t.length();

         for(char c:t.toCharArray()){

             map.put(c,map.containsKey(c)?map.get(c)+1:1);

         }

         int left=0;

         for(int right=0;right<s.length();right++){

             char val=s.charAt(right);

             if(map.containsKey(val)){

                 map.put(val,map.get(val)-1);

                 if(map.get(val)>=0){

                     count--;

                 }

             }

             while(count==0){

                 if(right-left<min){

                     min=right-left;

                     minStart=left;

                     minEnd=right;

                 }

                 char temp=s.charAt(left);

                 if(map.containsKey(temp)){

                     map.put(temp,map.get(temp)+1);

                     if(map.get(temp)>0) count++;

                 }

                 left++;

             }

         }

         return min==Integer.MAX_VALUE?"":s.substring(minStart,minEnd+1);

     }

 }

巴特西

Leetcode 76.最小覆盖子串

最小覆盖子串

最新文章

热门文章