侧边栏壁纸
博主头像
小鱼吃猫博客博主等级

你所热爱的,便是你的生活。

  • 累计撰写 114 篇文章
  • 累计创建 47 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

3.无重复字符的最长子串

小鱼吃猫
2023-10-13 / 0 评论 / 2 点赞 / 42 阅读 / 3286 字

原题

3.无重复字符的最长子串

题目描述

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

示例

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

解析

方法一:

  • 原理

这是一道经典的动态规划题目,最简单的理解是求出每个字符为结尾不重复的最长子串。步骤如下:

  1. 定义一个数组dp,数组中的第i个字符结尾时的最长子串,这个数组中的每一项默认是s[i]
  2. 遍历字符串s,计算并填充dp中的每一项。
    2.1 找到s[i]是否存在于dp[i]的字符串中?
    如果存在,返回从右往左数位置r_index,则从dp[i]的r_index开始,和当前s[i]就可以组成新的不重复子串。
    2.2 如果不存在,则直接把当前字符串与之前的子串进行拼接dp[i]=dp[i-1]+s[i]。
  3. 遍历dp数组,寻找最长的字符串即可。
  • 代码

python

def lengthOfLongestSubstring(self, s: str) -> int:
    n = len(s)
    if n<2:
        return n
    # 防止报None
    dp=list(s)
    # 直接从第1个开始
    for i in range(1,n):
        r_index = dp[i-1].rfind(s[i])
        if r_index>-1:
            # 当前字符存在于上一个子串的r_index位
            dp[i]=dp[i-1][r_index+1:]+s[i]
        else:
            # 不存在,直接相加
            dp[i]=dp[i-1]+s[i]
    #  返回最大长度的子串
    return max([len(ss) for ss in dp])

Java

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    if (n < 2) {
        return n;
    }
    String[] dp = new String[n];
    dp[0] = s;
    for (int i = 1; i < n; i++) {
        int r_index = dp[i - 1].lastIndexOf(s.charAt(i));
        if (r_index > -1) {
            dp[i] = dp[i - 1].substring(r_index + 1) + s.charAt(i);
        } else {
            dp[i] = dp[i - 1] + s.charAt(i);
        }
    }
    int maxLength = 0;
    for (String ss : dp) {
        maxLength = Math.max(maxLength, ss.length());
    }
    return maxLength;
}

方法二:

定义了一个数组dp,来保存以每个字符结尾的最长不重复子串,但在这个数组中,真正用到的只有dp[i-1]这一个子串的长度,所以简化一下,只上一次子串的长度last_len。

  • 代码

python

def lengthOfLongestSubstring(self, s: str) -> int:
    if len(s)==0:
        return 0
    max_len = 1
    last_len = 1
    for i in range(1,len(s)):
        max_arr = s[i-last_len:i]
        print(max_arr,s[i])
        r_index = max_arr.rfind(s[i])
        if len(max_arr)>0 and r_index>-1:
            #  存在
            last_len = last_len-r_index
        else:
            # 不存在
            last_len += 1
            max_len = max(last_len, max_len)
    return max_len

Java

public int lengthOfLongestSubstring(String s) {
    if (s.isEmpty()) {
        return 0;
    }
    int maxLength = 1;
    int lastLength = 1;
    for (int i = 1; i < s.length(); i++) {
        String maxArr = s.substring(i - lastLength, i);
        System.out.println(maxArr + " " + s.charAt(i));
        int rIndex = maxArr.lastIndexOf(s.charAt(i));
        if (maxArr.length() > 0 && rIndex > -1) {
            // 存在
            lastLength = lastLength - rIndex;
        } else {
            // 不存在
            lastLength++;
            maxLength = Math.max(lastLength, maxLength);
        }
    }
    return maxLength;
}
2

评论区