leetcode 438. 找到字符串中所有字母异位词 [PHP]

438. 找到字符串中所有字母异位词

    function findAnagrams($s, $t) {
        $ret = [];
        $needs = $windows = [];
        $len_s = strlen($s);
        $len_t = strlen($t);
        $left = $right = 0;
        for ($i = 0; $i < $len_t; $i++) {
            $needs[$t[$i]]++;
        }
        $match = 0;
        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 == $len_t) {
                    $ret[] = $left;
                }
                $l_str = $s[$left];
                if (isset($needs[$l_str])) {
//                    if (--$windows[$l_str] != $needs[$l_str]) {
//                        $match--;
//                    }
                    if (--$windows[$l_str] < $needs[$l_str]) {
                        $match--;
                    }
                }
                $left++;
            }
        }
        return $ret;
    }

跟之前的滑动窗口一个模板，只不过是在试图改变窗口left时检测的条件不一样。另外这里的异位词竟然包括顺序也相同的词。。。。

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