LeetCode 3. Longest Substring Without Repeating Characters
暴力算法: 找出所有的字字符串并且檢查是否有重復乍构，然后選擇最大值
Sliding Windows: 使用字典存儲字符串s[i,j]中所有字符的位置察绷，result = max(result, j-i) .如果遇到重復的字符, 將i更新為i+1炮叶，繼續(xù)循環(huán)直到i到s的末端。
-
Improved Sliding Windows: 使用字典存儲字符最新的位置贷揽，result = max(result, j-i). 如果遇到重復的字符,將i更新為重復的字符上一次出現(xiàn)的位置+1棠笑。更新字典中這個字符的位置，繼續(xù)循環(huán)直到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:
-
s[j] in char_dict:
檢查字典char_dict中是否存在key為s[j]的記錄。
原帖
