首页 > 代码库 > [leetcode]Longest Substring Without Repeating Characters @ Python
[leetcode]Longest Substring Without Repeating Characters @ Python
原题地址：https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
题意：Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
解题思路：使用一个哈希表，记录字符的索引。例如对于字符串‘zwxyabcabczbb‘，当检测到第二个‘a‘时，由于之前已经有一个‘a‘了，所以应该从第一个a的下一个字符重新开始测算长度，但是要把第一个a之前的字符在哈希表中对应的值清掉，如果不清掉的话，就会误以为还存在重复的。比如检测到第二个‘z‘时，如果第一个‘z‘对应的哈希值还在，那就出错了，所以要把第一个‘a‘之前的字符的哈希值都重置才行。
代码：
class Solution: # @return an integer def lengthOfLongestSubstring(self, s): start = 0 maxlen = 0 hashtable = [-1 for i in range(256)] for i in range(len(s)): if hashtable[ord(s[i])] != -1: while start <= hashtable[ord(s[i])]: hashtable[ord(s[start])] = -1 start += 1 if i - start + 1 > maxlen: maxlen = i - start + 1 hashtable[ord(s[i])] = i return maxlen
class Solution: # @return an integer def lengthOfLongestSubstring(self, s): start = 0 maxlen = 0 dict = {} for i in range(len(s)): dict[s[i]] = -1 for i in range(len(s)): if dict[s[i]] != -1: while start <= dict[s[i]]: dict[s[start]] = -1 start += 1 if i - start + 1 > maxlen: maxlen = i - start + 1 dict[s[i]] = i return maxlen
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。