題目

  • 題目連結
  • 目標函式 : lengthOfLongestSubstring(s)
    • Input : s: str
    • Output : int

解題概念

  • 題意 : 給定一字串 s，需要回傳最長 Substring 的長度(不包含重複字元)

我的寫法

  • 想法 :
    • max_value : 儲存目前累積的最長長度
    • temp_str : 暫存每回合的 Substring
    • 使用 for 迴圈去判斷每個字元 c :
      • 若 c 已出現在 temp_str 中 : 代表出現重複字元
        1. 更新當前 max_value
        2. 將 temp_str 當中索引值為 0 ~ temp_str.index(c)] 移除
      • 再將 c 加到 temp_str 後方
    • 最後回傳 max(max_value, len(temp_str))
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def lengthOfLongestSubstring(self, s):
        
        if len(s) == 0: return 0

        max_value = -1
        temp_str = ""
        for c in s:
            if c in temp_str:
                max_value = max(max_value, len(temp_str))
                temp_str = temp_str[temp_str.index(c)+1:]
            temp_str += c
        return max(max_value, len(temp_str))
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 33 ms (faster than 81.46%)
    • Memory Usage: 13.5 MB (more than 85.14%)

解答 or 其他優秀寫法

  • 想法 : 使用 Hashmap seen 去儲存已看過的字元
    • 儲存格式 :
      • key : 已看過的字元
      • value : 該字元位於 s 的索引值
    • 使用參數 :
      • left : 當作是 temp_str 第一個字元的索引值
    • 使用 for 迴圈去判斷每個字元 s[right] :
      • 若 s[right] 已被看過 + left <= seen[s[right]] (即 temp_str 為空) :
        • 則更新 left : 將其設為 seen[s[right]] + 1
      • 否則，更新 max_value 即可
    • 最後將 seen 中 s[right] 的 value 設為 right
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def lengthOfLongestSubstring(self, s):
        
        if len(s) == 0: return 0

        seen = dict()
        left = 0
        max_value = 0

        for right in range(len(s)):
            if s[right] in seen and left <= seen[s[right]]:
                left = seen[s[right]] + 1
            else:
                max_value = max(max_value, right - left + 1)
            
            seen[s[right]] = right
            
        return max_value
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 35 ms (faster than 76.43%)
    • Memory Usage: 14.2 MB (more than 42.81%)