[leetcode algorithms]題目3

3. Longest Substring Without Repeating Characters

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.

自己寫的代碼：

遍歷字元串，用列表存儲已經被遍歷且不重複的字元，遍歷下一個字元的時候判斷一下這個字元是否在列表中，如果在的話，就把列表中的這個字元以及這個字元前面的字元都刪掉。運行時間145ms。也試過用字典存儲已經遍歷過的字元及其下標，雖然判斷字元是否在字典中存在的時候效率會高一些，但是遇到重複字元的時候更新字典的效率卻很低。運行時間高達314ms，最後還是放棄了字典，使用列表。

class Solution: def lengthOfLongestSubstring(self, s): sub = [] res = 0 for char in s: if char in sub: res = max(res, len(sub)) sub = sub[sub.index(char)+1:] sub.append(char) res = max(res, len(sub)) return res

受討論區啟發後寫的代碼：

思路也是用字典，但是不去更新這個字典，我只想到了字典，但是非得要更新它。遇到重複字元之後，還要判斷重複的字元的下標是否大於不重複字元串的起始下標。這個思路確實妙啊。

class Solution: def lengthOfLongestSubstring(self, s): if s is "": return 0 dic = {} res = start = 0 for i, char in enumerate(s): if char in dic: j = dic[char] if j >= start: res = max(res, i - start) start = j + 1 dic[char] = i res = max(res, i + 1 - start) return res

而討論區的代碼更加簡潔，雖然在沒有遇到重複的時候也在計算最大長度，有點浪費計算，但實際運行時效率並沒有差異。

class Solution: # @return an integer def lengthOfLongestSubstring(self, s): start = maxLength = 0 usedChar = {} for i in range(len(s)): if s[i] in usedChar and start <= usedChar[s[i]]: start = usedChar[s[i]] + 1 else: maxLength = max(maxLength, i - start + 1) usedChar[s[i]] = i return maxLength

推薦閱讀：