最小覆盖子串
给定一个字符串 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);
- }
- }
来源: http://www.bubuko.com/infodetail-2894104.html