Leetcode3:Longest Substring Without Repeating Characters@Python

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring

首先我解这个题的思路是依次找到一个字符串的所有字串，和已存的LongestSubstring比较长度，如大于，替换，直至找到所有的字串。

我的这个程序可能还有问题，提交后显示为 Time Limit Exceeded（超时），不过我有时间会改下它，找到错误。

 1 class Solution(object):
 2     def lengthOfLongestSubstring(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         longestSubstring = ''
 8         strLength = len(s)
 9         longestSubstringLength = 0
10         for i in range(strLength):
11             subString = ''
12             str = s[i:strLength]
13             for j in range(len(str)):
14                 if str[j] not in subString:
15                     subString += str[j]
16                     if j == len(str)-1:
17                         substringLength = len(subString)
18                         if substringLength>longestSubstringLength:
19                             longestSubstringLength = substringLength                        
20                             longestSubstring = subString
21                 else:
22                     substringLength = len(subString)
23                     if substringLength>longestSubstringLength:
24                         longestSubstringLength = substringLength                        
25                         longestSubstring = subString
26                     break
27         return longestSubstringLength

在网上我找到了另外的对于Python特别方便的解法：开一个字典记录字符串中的字符和它的索引，left用来记录当前字符最新出现的地方。

 1 class Solution(object):
 2     def lengthOfLongestSubstring(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         res = 0
 8         left = 0
 9         d = {}
10         for i,ch in enumerate(s):
11             if ch in d and d[ch] >= left:
12                 left = d[ch] + 1
13             d[ch] = i
14             res = max(res,i - left + 1)
15         return res

Leetcode3:Longest Substring Without Repeating Characters@Python

推荐阅读