遙かなるマチョジニア

マッチョXエンジニアを目指すブログ

【LeetCode】Longest Substring Without Repeating Characters 解法【Python】

スポンサードリンク

Longest Substring Without Repeating Characters

leetcode.com

与えられた文字列内で、文字が重複しない範囲の最大の文字数を返却する。

解法

1文字見ていって、重複した時点の1文字前までの文字数を最大候補として、 重複した文字の最初に出てきた場所から再度カウントし直す。 それを繰り返して最大候補の中から最大文字数を返却する。

f:id:shuheilocale:20200529072946p:plain

毎回、重複した文字の最初に出てきた文字まで戻るのはコストなので、 その場所を覚えておき、現在の場所までの文字列をスライス、みたいなふうにして高速化。

コード

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        if s == "":
            return 0
        if len(set(s)) == len(s):
            return len(s)
        
        max_len = str_len = 1
        local_s = [s[0]]
        s_idx = 0
        for i in range(1, len(s)):

            if s[i] in local_s:   
                str_len = i - s_idx
                max_len = max(max_len, str_len)
                
                find_idx = local_s.index(s[i])
                s_idx = find_idx+s_idx+1
                local_s = local_s[find_idx+1:]
            
            local_s.append(s[i])
        else:
            str_len = len(s) - s_idx
            max_len = max(max_len, str_len)
                
        return max_len
            

f:id:shuheilocale:20200529071442p:plain

f:id:shuheilocale:20200529071621p:plain

ハッシュ使ったらもっと速そう。

solutionに書いていたシンプルなコード(にちょっとだけ手を加えて高速化したもの)

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        str_list = []
        max_length = 0

        for x in s:
            if x in str_list:
                max_length = max(max_length, len(str_list))
                str_list = str_list[str_list.index(x)+1:]
            str_list.append(x)    
        else:
            max_length = max(max_length, len(str_list))

        return max_length

さらに、solutionに書いていた、めちゃ速い解法。 やはりdict使っている。

class Solution:
    def lengthOfLongestSubstring(self, s):
        dicts = {}
        maxlength = start = 0
        for i,value in enumerate(s):
            if value in dicts:
                sums = dicts[value] + 1
                if sums > start:
                    start = sums
            num = i - start + 1
            if num > maxlength:
                maxlength = num
            dicts[value] = i
        return maxlength