LeetCode76--最小覆盖子串-蒲公英云

LeetCode76--最小覆盖子串

给你一个字符串 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 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

解法一滑动窗口

用双指针 left 和 right 表示一个窗口。

right 向右移增大窗口，直到窗口包含了所有要求的字母。进行第二步。
记录此时的长度，left 向右移动，开始减少长度，每减少一次，就更新最小长度。直到当前窗口不包含所有字母，回到第 1 步。

<?php

class Solution {
```
/**
 * @param String $s
 * @param String $t
 * @return String
 */
function minWindow($s, $t) {
    if(strlen($s)<strlen($t)){
        return "";
    }
```

        $map = [];
        //遍历字符串$t，初始化每个字母的次数
        for($i=0; $i<strlen($t); $i++){
            $map[$t[$i]]++;
        }
        $left = 0;//左指针
        $right = 0;//右指针
        $ans_left = 0;//保存最小窗口的左边界
        $ans_right = -1;//保存最小窗口的右边界
        $ans_len = PHP_INT_MAX;//当前最小窗口的长度
        $flag = false;//是否能匹配到的标志
        //遍历字符串$s
        while ($right<strlen($s)){
            if(isset($map[$s[$right]])){
                $map[$s[$right]]--;
                while ($this->match($map)){
                    $flag = true;
                    //当前窗口大小
                    $tmp_len = $right-$left+1;
                    if($tmp_len<$ans_len){
                        $ans_left = $left;
                        $ans_right = $right;
                        $ans_len = $tmp_len;
                    }
                    //判断$map中是否有当前字母
                    if(isset($map[$s[$left]])){
                        //因为要把当前字母移除，所以相应次数要加1
                        $map[$s[$left]]++;
                    }
                    //左指针右移
                    $left++;
                }
            }
            //右指针右移扩大窗口
            $right++;
        }
        if($flag){//匹配到了
            return substr($s, $ans_left, $ans_len);
        }else{//未匹配到
            return "";
        }
    }
    //判断所有的$v是否为0
    function match($map){
        foreach ($map as $v){
            if($v>0){
                return false;
            }
        }
        return true;
    }
}

时间复杂度：O（nm），n 是 S 的长度，match 函数消耗 O（m）。
空间复杂度：O（m），m 是 T 的长度。

此外，判断当前窗口是否含有所有字母，我们除了可以判断所有字母的次数是否小于等于 0，还可以用一个计数变量 count，把 count 初始化为 t 的长度，然后每次找到一个满足条件的字母，count 就减 1，如果 count 等于了 0，就代表包含了所有字母。这样的话，可以把之前的 match(map) 优化到 O（1）。

class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return String
     */
    function minWindow($s, $t) {
        $s_len = strlen($s);
        $t_len = strlen($t);
        if($s_len<$t_len){
            return "";
        }
        $map = [];
        //遍历字符串$t，初始化每个字母的次数
        for($i=0; $i<$t_len; $i++){
            $map[$t[$i]]++;
        }
        $left = 0;//左指针
        $right = 0;//右指针
        $ans_left = 0;//保存最小窗口的左边界
        $ans_right = -1;//保存最小窗口的右边界
        $ans_len = PHP_INT_MAX;//当前最小窗口的长度
        $flag = false;//是否能匹配到的标志
        //遍历字符串$s
        while ($right<strlen($s)){
            if(isset($map[$s[$right]])){
                //当前字母次数减一
                $map[$s[$right]]--;
                if($map[$s[$right]]>=0){
                    //代表当前符合了一个字母
                    $t_len--;
                }
                //echo $left.'--'.$right.'--'.$t_len.PHP_EOL;
                while ($t_len == 0){
                    $flag = true;
                    //当前窗口大小
                    $tmp_len = $right-$left+1;
                    if($tmp_len<$ans_len){
                        $ans_left = $left;
                        $ans_right = $right;
                        $ans_len = $tmp_len;
                    }
                    //判断$map中是否有当前字母
                    if(isset($map[$s[$left]])){
                        //因为要把当前字母移除，所以相应次数要加1
                        $map[$s[$left]]++;
                        if($map[$s[$left]]>0){
                            $t_len++;
                        }
                    }
                    //左指针右移
                    $left++;
                }
            }
            //右指针右移扩大窗口
            $right++;
        }
        if($flag){//匹配到了
            return substr($s, $ans_left, $ans_len);
        }else{//未匹配到
            return "";
        }
    }
}