[leetcode]Longest Substring Without Repeating Characters @ Python

浏览数：24 / 时间：2015年06月08日

原题地址：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