主題

LeetCode - 3. Longest Substring Without Repeating Characters 解題心得

Not In My Back Yard | 2021-04-16 00:30:00 | 巴幣 0 | 人氣 47

題目連結:


題目意譯:
給定一字串 s ,請找到最長的、沒有重複字元的字串之長度。

限制:
0 ≦ s.length ≦ 5 × 10 ^ 4
s 由英文字母、數字、符號以及空白組成。



範例測資:
範例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 答案為 "abc",其長度為 3。

範例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 答案為 "b",其長度為 1。

範例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 答案為 "wke",其長度為 3。
注意,答案須為一子字串,"pwke" 為一子序列而非子字串。

範例 4:
輸入: s = ""
輸出: 0


解題思維:
令 D[i] 定為在選取 s[i] 的情況下,s[0] ~ s[i] 的最長無重複字元子字串(或其長度)。

可以看到如果 s[i] 不存在於 D[i-1] 中,則 D[i] = D[i-1] + s[i];反之,D[i] = D[i-1]' + s[i],其中 D[i-1]' 代表去除掉先前的 s[i] 以及其前面的所有字元之字串。

而我們可以用一個陣列 L,來儲存每種字元上一次出現於何處(初始化的值可以設為 -1,代表根本就還沒出現過),還有一變數 b 代表著「D[i-1]」之解的開頭位置。

當我們看到 L[s[i]] ≧ b 時,代表 s[i] 已經出現於 D[i-1] 的解中了。此時我們將 b 設為 L[s[i]] + 1,即可得到 D[i];反之,D[i] = D[i-1] + s[i]。判斷完之後,記得將 L[s[i]] 之值設為 i,代表著 s[i] 現在出現於位置 i。

而所求即是所有可能的 D[i] 之長度裡面最大的。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作