题解 | #最小覆盖子串#

最小覆盖子串

http://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

题意整理

给出两个字符串s和t，要求在s中找出最短的包含t中所有字符的连续子串。

方法一（暴力循环）

1.解题思路

首先统计T中所有字符出现次数，记录在map1中。
然后两层循环遍历S中所有连续子串，对每一个子串，统计字符出现次数，记录在map2中。
每次判断某个子串是否包含t中所有字符，如果包含，则更新子串长度len和起始点start。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        //n为S的长度，m为T的长度
        int n=S.length();
        int m=T.length();
        //记录子串长度
        int len=10001;
        //记录子串起始点
        int start=0;
        //统计T中字符出现次数
        int[] map1=new int[128];
        for(int i=0;i<m;i++){
            map1[T.charAt(i)]++;
        }
        for(int i=0;i<n;i++){
            //统计子串字符出现次数
            int[] map2=new int[128];
            for(int j=i;j<n;j++){
                map2[S.charAt(j)]++;
                //如果合法，并且长度小于len
                if(match(map1,map2)&&len>j-i+1){
                    //更新len和起始点
                    len=j-i+1;
                    start=i;
                }
            }
        }
        return len==10001?"":S.substring(start,start+len);
    }
    
    //判断子串是否包含T中所有字符
    private boolean match(int[] map1,int[] map2){
        for(int i=0;i<128;i++){
            //只要某个字符，T中出现次数更多，则不合法
            if(map1[i]>map2[i]){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

时间复杂度：假设n为S的长度，m为T的长度,统计T中字符出现次数需要遍历整个T字符串，时间复杂度 $O (m)$ 。两层循环枚举所有可能的连续子串，总共 $n * (n + 1) / 2$ 个，match函数的复杂度为常数级别，所以时间复杂度为 $O (n^{2} + m)$ 。
空间复杂度：需要额外大小128的map1和map2数组，均为常数级别，所以空间复杂度是 $O (1)$ 。

方法二（双指针）

1.解题思路

首先统计T中所有字符出现次数，记录在map中。
定义两个变量l和r分别记录子串的起点和终点。定义一个变量count用于统计T中字符是否能在对应子串完全消除，如果能，则子串合法，否则，不合法。
如果右边界对应字符次数大于0，说明需要消去当前字符，r右移，map对应次数减1，同时count减1。只要count为0时，说明字符全部消除掉，当前子串合法，跟新子串长度和起始点。如果左边界对应字符次数等于0，说明需要重新消去当前字符，l右移，右移之后，map对应次数加1，计数count也需要加1。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        //n为S的长度，m为T的长度
        int n=S.length();
        int m=T.length();
        //记录子串长度
        int len=10001;
        //记录子串起始点
        int start=0;
        //统计T中字符出现次数
        int[] map=new int[128];
        for(int i=0;i<m;i++){
            map[T.charAt(i)]++;
        }
        //滑动窗口的左右边界l和r，以及待消除的字符数量count
        int l=0,r=0,count=m;
        while(r<n){
            //如果出现次数大于0，说明需要消除，count减1
            if(map[S.charAt(r++)]-->0){
                count--;
            }
            //只要count为0，说明当前子串合法
            while(count==0){
                //如果长度小于len，则更新len和start
                if(len>r-l){
                    len=r-l;
                    start=l;
                }
                //如果左边界字符出现次数为0（要么小于0，要么等于0），则需要重新消除，后移l
                if(map[S.charAt(l++)]++==0){
                    //后移之后，count需加1
                    count++;
                }
            }
        }
        return len==10001?"":S.substring(start,start+len);
    }
    
}