3.重複文字のない長男列(Python)

タイトル
文字列を指定すると、重複文字が含まれていない長男の列の長さを見つけてください.
例
例1:
入力:“abcabcbb”出力:3解釈:重複文字のない最長男列は“abc”であるため、その長さは3である.
例2:
入力:「bbbbb」出力:1解釈:重複文字のない長男列は「b」であるため、その長さは1である.
例3:
入力:「pwwkew」出力:3解釈:重複文字のない長男列は「wke」であるため、その長さは3である.あなたの答えはサブストリングの長さでなければなりません.「pwke」はサブストリングであり、サブストリングではありません.
に答える
シナリオ1
まず,暴力的解法を用いて,文字列の各サブ列に重複文字が含まれていないかどうかを探究し,重複文字が含まれていない最長子列を記録することを考慮する.ここで、i,jは、元の文字のサブ列の両端文字のインデックスを設定し、lambda式で簡易関数no_を定義するrepetitive_charsは、入力した文字列に重複文字がないかどうかを判断し、Trueを返さない場合に使用します.cur_でlen現在の重複しない文字列の長さをmax_で記録するlenは、現在までの最大非繰返しサブ列長を記録する.すべてのサブストリングの可能性は(N+1)*N/2個であり,一つ一つ判断する必要がある.

class Solution:
    def lengthOfLongestSubstring(self, s):
        no_repetitive_chars = lambda s: len(list(cur_chars)) == len(set(list(cur_chars)))
        max_len = 0
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                cur_chars = s[i:j]                      #      
                if no_repetitive_chars(cur_chars):
                    cur_len = len(cur_chars)            #       
                    max_len = max(cur_len, max_len)     #         
        return max_len

予想外に、コードがタイムアウトしたので、考えを変える必要があります.
シナリオ2
どのようにして一度だけ遍歴しますか?より良い時間性能を得るために、アルゴリズム最適化でよく使われる空間で時間を変える戦略を採用し、入力文字列をsとし、文字列を最初から最後まで遍歴する:1.一時文字列変数cur_の作成str、この文字列には重複文字がなく、最後の文字は現在遍歴している文字です.2.下付き辞書(ハッシュ表)index_の定義dict、辞書のキーはcur_ですstrの各文字は、文字に対応するsの下付き文字である.3.文字列を最初から最後まで巡回し、現在の文字列cur_を表示charはcur_にあるかどうかstrで、表示された場合、辞書から文字の位置prev_を取り出します.index、cur_を保証するためにstrの要素は繰り返されず、cur_をstrの最初の文字の開始位置start_index(sに対して)prev_に移動index+1、prev_からindex+0.5位置カットオフcur_strは後半を併取する.4.同時に下付き辞書index_を更新するdict、start_に削除indexより前のすべての文字レコード、index_を確認dictのすべての要素はcur_のみを含むstrのすべての文字.気をつけなければならないのはstart_index,prev_index,cur_Indexなどの下付き変数はいずれも入力文字sに対する位置である.

class Solution(object):
    def lengthOfLongestSubstring(self, s):

        def remove_previous_chars(index_dict, index):
            previous_chars = []
            for char in index_dict.keys():
                if index_dict[char] < index:
                    previous_chars.append(char)
            for char in previous_chars:
                index_dict.pop(char)
        #    {key: value for key, value in index_dict.items() if value >= index}
        #            

        if s is None or len(s) == 0:                            #     ，    
            return 0

        max_len = start_index = 0
        index_dict = {}                                         #     ，key   ，value   

        for cur_index in range(len(s)):
            cur_char = s[cur_index]                             #     
            if cur_char in index_dict:
                start_index = index_dict[cur_char] + 1          #             
                remove_previous_chars(index_dict, start_index)  #       
            # cur_str = s[cur_index: start_index+1]             #      
            # cur_len = len(cur_str)                            #        
            cur_len = cur_index - start_index + 1               #        
            index_dict[cur_char] = cur_index                    #           
            max_len = max(max_len, cur_len)                     #       
        return max_len

コードは時間制限を通過し、280 msかかります.
シナリオ3
辞書の要素を繰り返し削除する必要はありませんか?ここで私たちの辞書index_dict特性の変化はcur_を記録するだけでなくstrのすべての文字は、現在の位置cur_に遍歴します.index以降のすべてのsに現れた文字とその距離cur_indexの最近の下付き文字.これでcurを勝手に更新できないことが要求されます.strの開始位置start_index、このときstart_を更新しますindexは、index_に現在の文字だけでなくdictに現れたことがあります.位置はprev_です.index、cur_に現れる位置を保証する必要がありますstrでは、前回の出現位置prev_が要求されます.index

class Solution(object):
    def lengthOfLongestSubstring(self, s):

        if s is None or len(s) == 0:
            return 0

        max_len = start_index = 0
        index_dict = {}

        for cur_index in range(len(s)):
            cur_str = s[cur_index]
            if cur_str in index_dict and index_dict[cur_str] >= start_index:
                start_index = index_dict[cur_str] + 1
            cur_len = cur_index - start_index + 1
            index_dict[cur_str] = cur_index
            max_len = max(max_len, cur_len)
        return max_len

コードは時間88 msを通過し、これもネット上で広く採用されている方法である.
何か質問があれば、コメントエリアのコメントを歓迎します.