题解 | #最小覆盖子串#

最小覆盖子串

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

题目：最小覆盖子串

描述：给出两个字符串S和T，要求在O(n)的时间复杂度内在S中找出最短的包含T中所有字符的子串。
例如：S="XDOYEZODEYXNZ"，T="XYZ"找出的最短子串为"YXNZ".

注意：如果S中没有包含T中所有字符的子串，返回空字符串“”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

示例1：输入："XDOYEZODEYXNZ","XYZ"，返回值："YXNZ"

解法一：

思路分析：只读题目，想到需要采用数据结构中的KMP算法，但是当看到例如后面的分析，立马停止了这种想法，在这道题当中，选择map关联式容器的方法进行分析，将字符与出现的次数进行关联。使用两个指针分别做窗口的左右边界，使有边界一直往后滑动，直到窗口中的字符子串覆盖t串后，判断左边界是否有多余，记录此时的窗口长度、起始下标，实时更新最短长度，最后尝试着移动左边界，重复右边界持续扩大的操作，一直循环执行。

实例分析："XDOYEZODEYXNZ","XYZ"，返回值："YXNZ"

首先设置两个指针，左指针和右指针，左指针不变，循环有指针到包含T中所有的字符

LEFT

RIGHT

该窗口正好包含T中所有元素，此时可求出一组长度为6的序列，移动LEFT到不包含T为止，再进行RIGHT的寻找

LEFT

输出这一组的长度为10，不进行更新，一直循环判断到……

LEFT

RIGHT

输出最终的子序列

"YXNZ"

具体C++代码为：

class Solution {
public:
    unordered_map <char, int> ori;//t字符的数量
    unordered_map <char, int> cnt;//当前区间包含的t中字符的数量
    bool check(){//检查现有区间是否已经包含目的串
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second){
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t){
        for (const auto &c: t){//初始化ori,t中字符及对应数量，X88,Y89,Z90
            ++ori[c];
        }
        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;
        while (r < int(s.size())){//r初始值-1，与size_t无法比较
            if (ori.find(s[++r]) != ori.end()){//s中找到一个t中的字符
                ++cnt[s[r]];
            }
            while (check()){
                if (r - l + 1 < len){ //更新答案
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()){ //左指针右移
                    --cnt[s[l]];
                }
                ++l;
            }
        }
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

最坏情况下左右指针对S的每个元素各遍历一遍，设字符集的大小为N，则渐进时间复杂度为O(N*s+t)，空间复杂度为O(N)。

解法二：

思路分析：我们可以分配一个大小为256的数组充当hashmap的作用，记录T中字母出现的次数，具体首先为将T中所有字符出现的次数保存在td数组中，遍历整个S字符串，开始设定两个值，分别为start表示当前字符串的起点，i表示当前字符串的终点，用found表示当前字符串中包含T中字符的数目，如果found = T.length()则表明当前字符串包含了T中全部的字符串，进入下一步，将start后移，取出start前面多余的元素，达到最小的目标。通过不断判断得出历史最小的子串，将当前子串的长度，起始点，结束点进行记录，最后输出。

具体java代码为：

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        if(S == null || S.length() == 0)//特殊情况，返回空字符串
            return "";
        if(T == null || T.length() == 0)
            return "";
        int[] td = new int[256];//设置td，保存T中所有字符出现的次数
        for(char tc : T.toCharArray())//字符串转换为字符数组
            td[tc]++;
        int[] sd = new int[256];
        int slen = S.length();
        int start = 0,first = -1,end = 0;//距离标志
        int found = 0;//在S中发现T元素的数目
        for(int i = 0;i < S.length();i++){
            sd[S.charAt(i)]++;//charAt(i)为第i个字符在字符串S中所占的位置
            if(sd[S.charAt(i)] <= td[S.charAt(i)]){//计算S的位置是否与T的位置相等
                found++;
            }
            if(found == T.length()){//满足条件
                while(start <= i && sd[S.charAt(start)] > td[S.charAt(start)]){
                    sd[S.charAt(start)]--;
                    start++;
                }
                //如果比当前最小子串小，则更新
                if(i + 1 - start <= slen){
                    slen = i + 1 - start;
                    first = start;
                    end = i+1;
            }
                sd[S.charAt(start)]--;
                start++;
                found--;
            }
        }
        if(first == -1){
            return "";
        }
        else{
            return S.substring(first, end);//返回最终子串的范围
        }
    }
}

在该程序中遍历S中的每一个元素进行判断，并且还需要开辟内存空间进行子串的存储，其时间复杂度为O(N)，设字符集的大小为N，则空间复杂度为O(N)。

算法自然分析文章被收录于专栏

在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。