首页 > 代码库 > Leetcode 3. Longest Substring without repeating characters
Leetcode 3. Longest Substring without repeating characters
思路:类似双指针,用left标定以当前字母结尾的最长无重的substring的起点。逐个扫描字母,如果这个字母当前的substring里面没有,那么当前的substring长度就可以加一。如果这个字母已经在substring里面了,例如:
当扫描到第二个c的时候,left应该移到d上来。并且应该将 C:2 更新为 C:6。 这里由于需要第一个c 的index,应该使用一个hash table。 如果cur后面又出现了一个a,由于目前a这个key的value小于left,所以说明current non repeating substring里面没有a。注意L14的条件。
1 class Solution(object): 2 def lengthOfLongestSubstring(self, s): 3 """ 4 :type s: str 5 :rtype: int 6 """ 7 8 ans = 0 9 left = 0 10 11 curStr = {} 12 13 for i in range(len(s)): 14 if s[i] in curStr and curStr[s[i]] >= left: 15 left = curStr[s[i]] + 1 16 17 curStr[s[i]] = i 18 19 ans = max(ans, i-left +1) 20 21 return ans 22
Leetcode 3. Longest Substring without repeating characters
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。