时间戳

首页 > 解决方案 > 了解leetcode中最长子串无重复问题的解决方案

python - 了解leetcode中最长子串无重复问题的解决方案

问题描述

所以我试图理解这个问题的解决方案。这里的目标是从字符串中获取最长子字符串的长度，而不需要重复的字符。

我的理解是，它是一个字符一个字符的。使用当前索引，它将从起始位置减去 0，因为索引最初从 0 开始。加 1 是为了补偿从索引 0 开始。

如果遇到重复字符，它将移动起始位置，直到找不到重复字符，这实际上将先前的字符分成一个子字符串，并从具有重复字符的新子字符串的位置开始，例如abcab => "abc" and "ab"。它将继续，直到找到长度最长且没有重复的子字符串。

解决方案的代码如下所示：

class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            used = {}
            max_length = start = 0
            
            for i,c in enumerate(s):
                if c in used and start<=used[c]:
                    start = used[c]+1
                else:
                    max_length = max(max_length,i-start+1)
                used[c] = i
            return max_length

我不明白的是这个解决方案start<=used[c]的used[c] = i一部分，它有什么作用？有人可以和我澄清一下吗？

编辑：我知道字典被用来跟踪字符数。我只是不明白它的逻辑。对不起，我应该澄清一下。

感谢您的阅读。

标签： python

解决方案

如果我理解正确，您的目标是形成最长的子字符串而不重复字符。

算法伪代码：

  1. 以空字符串开头，start作为字符串的开始索引。您想扩展字符串，直到获得重复字符。

  2. 每个角色有 2 种可能性，第一次看到角色或之前已经看到角色。在每个字符之后，我们更新书签used以跟踪上次看到的索引。

  3. a) 如果之前没有看到该字符，您可以安全地扩展当前字符串。

    或者

    b) 如果该字符之前出现过，那么我们只能扩展该字符串，如果它不是当前字符串的一部分（start > used[c]）。如果是start <= used[c]字符串（由于您在后一种情况下缩短了字符串，因此最大字符串不会在此位置结束。startstart = used[c] + 1

推荐阅读