leetcode 76、最小重复子串[PHP]

滑动窗口76、最小重复子串[PHP]

最小覆盖子串

    function minWindow($s, $t) {
        $left = $right = 0;
        $len_s = strlen($s);
        $len_t = strlen($t);
        $needs = $windows = [];
        $match = 0;
        $minIndex = PHP_INT_MAX;
        $minLen = PHP_INT_MAX;
        for ($i = 0; $i < $len_t; $i++) {
            $needs[$t[$i]]++;
        }

        while($right < $len_s) {
            $r_str = $s[$right];
            if (isset($needs[$r_str])) {
                $windows[$r_str]++;
                if ($windows[$r_str] == $needs[$r_str]) {
                    $match++;
                }
            }
            $right++;

            //试图缩小窗口
            while ($match == count($needs)) {
                if ($right- $left < $minLen) {
                    $minLen = $right - $left;
                    $minIndex = $left;
                }
                $l_str = $s[$left];
                if (isset($needs[$l_str])) {
                    $windows[$l_str]--;
                    if ($windows[$l_str] < $needs[$l_str]) {
                        $match--;
                    }
                }
                $left++;
            }

        }

        return $minLen == PHP_INT_MAX ? "" : substr($s, $minIndex, $minLen);
    }

文章永久链接：https://tech.souyunku.com/45142