• 1

  • 457

  • 收藏

最长不含重复字符的子字符串|刷题打卡

3星期前

一、题目描述:

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

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

示例 2:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

二、思路分析

看完题的第一想法就是动态滑块

  1. 把i-j之间的字符串存起来,存在一个队列中,$maxDiffStr,方便下次查验

  1. 继续向后找,直到找到$maxDiffStr中存在的值

  2. 将队列$maxDiffStr依次弹出,直到弹出的值与当前循环的值相等

  3. 此时重新计算maxLen

三、代码编写

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $len = strlen($s);
        if ($len < 1) {
            return 0;
        }

        $maxLen = 1;
        $maxDiffStr = [$s[0]];
        for ($i=1; $i < $len; $i++) {
            if (in_array($s[$i], $maxDiffStr)) {  
                while (array_shift($maxDiffStr) !== $s[$i]) {}
            }
            $maxDiffStr[] = $s[$i];
            $maxLen = $maxLen > count($maxDiffStr) ? $maxLen : count($maxDiffStr);
        }
        return $maxLen;
    }
}
复制代码

看了大佬的题解,果然更好的方法还差很远

双指针+哈希表

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $dic = [];
        $res = 0;
        $i = -1;
        $len = strlen($s);
        for ($j=0; $j < $len; $j++) {
            if (isset($dic[$s[$j]])) {
                $i = max($dic[$s[$j]], $i);
            }
            $dic[$s[$j]] = $j;
            $res = max($res, $j-$i);
        }
        return $res;
    }
}
复制代码

刷题打卡第一天,小菜菜在路上。。。

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

php

457

相关文章推荐

未登录头像

暂无评论