leetcode 3. Longest Substring Without Repeating Characters （python）

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第19天，點選檢視活動詳情

描述

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Note:

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces.

解析

根據題意， 給定一個字串 s ，找出含有不重複字元的最長子字串的長度。

這道題的題意是簡潔明瞭的，而且我們只要有經驗，碰到這種題為了保證時間複雜度符合 AC 要求，肯定要使用滑動視窗的解法，這樣才能在 O(N) 時間複雜度下完成解題。方向我們已經有了，具體思路如下：

• 定義 result 為最終結果， L 為滑動視窗的最左端索引，d 為儲存每個遍歷過的的字元的索引位置
• 遍歷 s 中所有的字元 c 其索引為 i ，如果這個字元沒有出現在 d 中，說明當前從 L 到 i 的子字串都沒有重複的，我們直接使用此子字串的長度更新 result ；如果 c 已經出現在了 d 中，並且 d[c] >= L ，那麼說明這個 c 字元出現在了從 L 到 i 的子字串中，此時我們將 L 更新為 d[c] + 1 即可，繼續後面的更新操作。每次遍歷更新每個字元最新的索引 d[c] = i 。
• 遍歷結束直接返回 result 即可

時間複雜度為 O(N) ，空間複雜度為 O(字元集合大小) 。

解答

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = 0
        L = 0
        d = {}
        for i, c in enumerate(s):
            if c in d and d[c] >= L:
                L = d[c] + 1
            else:
                result = max(result, i - L + 1)
            d[c] = i
        return result

執行結果

Runtime: 38 ms, faster than 94.63% of Python online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 13.8 MB, less than 62.00% of Python online submissions for Longest Substring Without Repeating Characters.

原題連結

http://leetcode.com/problems/longest-substring-without-repeating-characters/

您的支援是我最大的動力