LeetCode 刷题之无重复字符最长子串

LeetCode 刷题之无重复字符最长子串

Chris Yue No Comment
Posts

题目:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

解题思路

设置子字符串 sub,初始化为空字符串。

设置游标 point,指向主字符串(参数)中第 n 个字符串位置,初始化 0
设置子字符串在主字符串中的游标 subPoint(头对头),初始化 0

增加游标 point 值,以及对应字符,检查其在子字符串中的位置 pos,如果不存在,则还不构成重复。这种情况,将对应字符追加到 sub,并且重新统计最大不重复子字符串长度 max

但如果 point 对应字符在子字符串中的位置 pos 有值,则要改变 subPoint 来一次重新统计。

最不需要动脑的想法,就是将 subPoint++,即将子字符串在主字符串上往后挪一格,但为了获得更好的性能,我们是否可以不一点点将 subPoint 往后移动?

答案是可以的,用例子最好说明:

ABCDCEFGH 这个字符串中,一开始,子字符串最多可以到 ABCD,往后遇到第一个重复字符 C,同时可以发现,C 出现在 ABCD 的第三位。很明显,如果 subPoint 只移动一格,也就是子字符串从 B 开始重新统计,是没有必要的,因为我们已经知道 B 后会有 C,而且这个 C 会跟第二个的 C 重复,而且这个 C 重复时,子字符串因为少了 A 反而字符长度还没有第一次统计的长度长,完全是浪费操作。

所以我们能不能利用之前已知的某些结果?当然是可以的。我们可以直接将 subPoint 移动到 C 之后开始统计,而 C 之后的位置,就是 subPoint + pos + 1,这里稍微处理一下,处理速度会获得第一个质的提升。

接下来,如果还是用偷懒的方式,我们只用再重新一个个字符拼凑子字符串,但实际上,重新统计子字符串,依然不用每次都从零开始。

直接用上面的例子说明。通过观察和思考,我们可以得出一个其实还算明显的结论:第一个 C 和第二 C 之间,是不可能出现重复字符串的(因为有的话,最早出现重复的就不是第二个 C 了),所以对于第 2 次子字符串统计来说,初始化子字符串就是从 第一个 C 到第二个 C 之间的字符(包含第二个 C,虽然包不包含没有太大影响,但毕竟又省去了一次循环)。 PHP 通过 substr 很容易做到。通过这步的处理,执行效率又会上升一个档次。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $point = 0;
        $subPoint = 0;
        $len = strlen($s);

        $max = 0;
        $sub = '';
        while ($point < $len) {
            $pos = strpos($sub, $s[$point]);
            if (false === $pos) {
                $sub .= $s[$point];
                ++$point;

                $max = max($max, strlen($sub));
            } else {
                ++$pos;
                $subPoint += $pos;
                if ($subPoint + $max > $len) {
                    return $max;
                }

                $sub = substr($sub, $pos).$s[$point];
                $point = $subPoint + strlen($sub);
            }
        }

        return $max;
    }
}

这次的执行效率打败了 96.8% 的人,内存占用更是侥幸打败了 100%,对自己相当满意(滑稽)。

看了 LeetCode 的官方解题思路,其中提到了关键词『滑动窗口』,其实就是上面两点结合后更简介的总结,即:如果目前找到的子字符串 s 中有一格字符 c ,已经与紧跟 s 后面的字符相同,则将 s 中字符 c 之前的字符删除(包括 c 本身),再一点点向后比较。是不是感觉有滑动的画面感了?

LeetCode 刷题之无重复字符最长子串 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

微信赞赏码

写作累,服务器还越来越贵
求分担,祝愿好人一生平安
天使打赏人

发表评论

43 − = 38