LeetCode 3. Longest Substring Without Repeating Characters

原题

1. 暴力算法: 找出所有的字字符串并且检查是否有重复，然后选择最大值

2. Sliding Windows: 使用字典存储字符串s[i,j]中所有字符的位置，result = max(result, j-i) .如果遇到重复的字符, 将i更新为i+1，继续循环直到i到s的末端。

3. Improved Sliding Windows: 使用字典存储字符最新的位置，result = max(result, j-i). 如果遇到重复的字符,将i更新为重复的字符上一次出现的位置+1。更新字典中这个字符的位置，继续循环直到j到s的末端。
   可以看出改进后的算法只遍历了一次s字符串。

   class Solution:
   def lengthOfLongestSubstring(self, s):
       """
       :type s: str
       :rtype: int
       """
       char_dict = {}
       result = 0
       i = 0
       length = len(s)
       for j in range(length):
           if s[j] in char_dict and char_dict.get(s[j]) >= i:
               i = char_dict.get(s[j]) + 1
           else:
               result = max(j-i+1,result)
   
           char_dict[s[j]] = j
   
       return result
   

Note:

1. s[j] in char_dict:
   检查字典char_dict中是否存在key为s[j]的记录。
   原帖