題目解釋
給定一個字串 s
,求最長且沒有重複 character 的 substring。
範例
- 輸入:
s = "abcabcbb"
- 輸出:
3
輸出是 3,因為最長的 substring 是 "abc"。
最佳解法
步驟
整段題目最重要的 pseudo code 長的像這樣:
start_char, end_char = s[left], s[right]
if end_char in substring:
substring.revome(start_char)
left += 1
else:
substring.add(end_char)
如果 end_char
出現在了我們維護 substring 的 set
裡的話,我們就把 start_char
移出 set
裡面。
Q: 為什麼要這樣做呢?
A: 因為我們沒辦法確認後面的 string 還有多長!
- 主角是
right
,它負責 traverse 整條 string - 配角是
left
,透過它來控制 window 的長度
除了這兩個 ptr 之外,我們還需要存 substring 的 set
以及記錄用的變數: max_sub_len
,因為最後 traverse 完時,set
裡面會是最新鮮的 substring 而非最長的 substring。
NOTE: left
跟 right
中間的那段就是所謂的滑動窗口 (silding window
)。
程式碼
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
substring = set()
max_sub_len = 0
for right in range(len(s)):
while s[right] in substring:
substring.remove(s[left])
left += 1
else:
substring.add(s[right])
max_sub_len = max(len(substring), max_sub_len)
return max_sub_len
時間複雜度
O(n)
,n 是 s
的字串個數。
空間複雜度
O(n)
。
結語
很順的把 if...else
中的 if
換成 while
後才發現…
python 的 while
居然可以搭配 else
(已知用火🔥) !!!
因為像 C/C++ 就不行,蛇蛇是真的直覺 🐍。
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26