Python Leetcode 3: Time limit exceeded

Question

我正在解决LeetCode问题https://leetcode.com/problems/longest-substring-without-repeating-characters/:

给定字符串s，求出最长子字符串的长度无重复字符

约束条件包括:

• 0 <= s.length <= 5 * 104
• s由英文字母、数字、符号和空格组成。

如果使用滑动窗口算法:

def lengthOfLongestSubstring(str):
# define base case
if (len(str) < 2): return len(str)
# define pointers and frequency counter
left = 0
right = 0
freqCounter = {} # used to store the character count
maxLen = 0
while (right < len(str)):
# adds the character count into the frequency counter dictionary
if (str[right] not in freqCounter):
freqCounter[str[right]] = 1
else:
freqCounter[str[right]] += 1
# print (freqCounter)
# runs the while loop if we have a key-value with value greater than 1. 
# this means that there are repeated characters in the substring. 
# we want to move the left pointer by 1 until that value decreases to 1 again. E.g., {'a':2,'b':1,'c':1} to {'a':1,'b':1,'c':1}
while (len(freqCounter) != right-left+1):
# while (freqCounter[str[right]] > 1): ## Time Limit Exceeded Error
print(len(freqCounter), freqCounter)
freqCounter[str[left]] -= 1
# remove the key-value if value is 0
if (freqCounter[str[left]] == 0):
del freqCounter[str[left]]
left += 1

maxLen = max(maxLen, right-left+1)
# print(freqCounter, maxLen)
right += 1

return maxLen
print(lengthOfLongestSubstring("abcabcbb")) # 3 'abc'

我得到了错误"时间限制超过"当我提交这个while循环时:

while (freqCounter[str[right]] > 1):

不是

while (len(freqCounter) != right-left+1): 

我认为第一个是访问字典中的元素，它的时间复杂度为0(1)。不确定为什么这个版本会比第二个版本慢得多。这似乎意味着我的方法在这两种情况下都不是最佳的。我认为滑动窗口将是最有效的算法;我执行错了吗?

Answer 1

您的算法运行时间接近某些测试的超时限制—我甚至在len(freqCounter)版本中获得了超时。您所尝试的两个条件之间的差异不会有太大的不同，因此我将研究更激烈的方法来提高算法的效率:

• 不计算字母出现的频率，而是存储最后找到该字符的位置的索引。这允许你一次更新left，避免了第二个循环，你必须在每个单位步骤降低频率。

• 执行del真的没有必要。

• 你也可以使用更多的python循环，比如enumerate

这是应用这些思想的代码更新(第一个是最重要的一个):

class Solution(object):
def lengthOfLongestSubstring(self, s):
lastpos = {}
left = 0
maxLen = 0
for right, ch in enumerate(s):
if lastpos.setdefault(ch, -1) >= left:
left = lastpos[ch] + 1
else:
maxLen = max(maxLen, right - left + 1)
lastpos[ch] = right
return maxLen

当您使用ASCII码而不是字符时，可以实现另一个提升，因为这时您可以使用列表而不是字典。由于代码挑战保证字符来自一个小的基本字符集，我们不需要考虑其他字符代码:

class Solution(object):
def lengthOfLongestSubstring(self, s):
lastpos = [-1] * 128
left = 0
maxLen = 0
for right, asc in enumerate(map(ord, s)):
if lastpos[asc] >= left:
left = lastpos[asc] + 1
else:
maxLen = max(maxLen, right - left + 1)
lastpos[asc] = right
return maxLen

当提交这个时，它在运行时间方面得分很高。