Go 和 PHP 获取字符串中最长无重复的字符串

Go 和 PHP 获取字符串中最长无重复的字符串

author: he xiaodong date: 2020-04-19

原文链接:go leetcode

无重复字符的最长子串

这是 LeetCode 第三题,题干如下:

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:   输入: “abcabcbb”   输出: 3   解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2:   输入: “bbbbb”   输出: 1   解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示例 3:   输入: “pwwkew”   输出: 3   解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。 来源:力扣

解题思路

常规思路:两层循环字符串,并且我们需要一个 Map字典 来标记哪些字符已经出现过,流程如下:

这个题目,其实主要的考点在于对滑动窗口的理解。

滑动窗口:滑动窗口是数组、字符串问题中常用的抽象概念。 窗口通常是在数组、字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开)。 而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j) 向右滑动 1 个元素, 则它将变为 [i+1, j+1)[i+1,j+1)(左闭,右开)。

那么借用滑动窗口的概念,如何来解题呢?我这里画了一张示意图,其中 [X,Y) 就是 滑动窗口

这里有一个注意点:当 Y 指向的字符在 [X,Y) 滑动窗口之间时,假设索引值为 index,这时候 X 是直接移动到 index+1 的位置。

Go 实现

func lengthOfLongestSubstring(s string) int {
    var Length int
    var s1 string
    x := 0
    y := 0
    s1 = s[x:y]
    for ; y < len(s); y++ {
        // strings.IndexByte 用于判断y对应的字符是否在[x,y)中,不存在返回-1
        if index := strings.IndexByte(s1, s[y]); index != -1 {
            // 如果存在的话,x直接跳到index的后一位
            x += index + 1
        }
        s1 = s[x : y+1]
        if len(s1) > Length {
            Length = len(s1)
        }
    }
    return Length
}

PHP 实现

function lengthOfLongestSubstring($s)
{
    $start = 0;
    $str = "";
    $count = 0;
    $length = strlen($s);
    $result = '';
    for($i = 0; $i < $length; $i++) {
        $index = stripos($str, $s[$i]);
        // 找到了字符
        if ($index !== false) {
            $start += $index + 1;
        }

        $str = substr($s, $start, $i+1-$start);

        if (strlen($str) > $count) {
            $count = strlen($str);
            $result = $str;
        }
    }
    return $result;
}

echo lengthOfLongestSubstring('abcabcbb'); // output: bac