LeetCode題解 - 3. Longest Substring Without Repeating Characters [Medium]

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

1. Code:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        set_words = set()
        list_word = []
        
        for c in s:
            if c in list_word:
                set_words.add(''.join(list_word))
                del list_word[:list_word.index(c) + 1]
            list_word.append(c)
        
        # Final word
        if len(list_word) > 0:
            set_words.add(''.join(list_word))
        
        # bigger length
        count = 0
        for word in set_words:
            if len(word) > count:
                count = len(word)
        
        return count

心得:
這題想了很久，直覺是用set()來做
不過第3點的結果是"wke"，所以又不是單純的疊字
"wke", "kew"  是一樣的
"abc", "bca", "cab" 也是算一樣的

嗯…感覺是set()那裡做太久了

2. Code:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0
        list_word = []
        
        for c in s:
            if c in list_word:
                if len(list_word) > max_length:
                    max_length = len(list_word)
                list_word = list_word[list_word.index(c) + 1:]
            list_word.append(c)
        
        return max_length if max_length > len(list_word) else len(list_word)

心得:
拿掉del，速度快蠻多的