0%
Loading ...

【Leetcode 筆記】 3. Longest Substring Without Repeating Characters

題目解釋

給定一個字串 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: leftright 中間的那段就是所謂的滑動窗口 (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++ 就不行,蛇蛇是真的直覺 🐍。

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.