30. Longest Substring Without Repeating Characters

4332 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ

  • 重複文字のない最長部分文字列(substring)の長さを返します.

  • 文字列Sの部分文字列は、文字列の連続部分を表す.
    たとえば、「aek」、「joo」および「ekj」は「baekjoon」の部分文字列であり、「bak」、「p」および「oone」は部分文字列ではない.


    • 1.スライドウィンドウとダブルポインタで寸法を調整する

    
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        
        for index, char in enumerate(s):
            #이미 등장했던 문자라면 'start' 위치 갱신
            if char in used and start <= used[char]:
                start = used[char] + 1
            
            else: #최대 부분 문자열 길이 갱신
                max_length = max(max_length, index - start + 1)
                
            #현재 문자의 위치 삽입
            used[char] = index
            
        return max_length

  • s=abcabcbと仮定

  • スライドウィンドウでセルを右側に移動し、ダブルポインタを使用してウィンドウのサイズを調整して、ウィンドウ内のすべての文字が重複しないようにします.結果は次のとおりです.
    • <文字列の一部を検索するダブルポインタプール>

  • この図では、重複文字のないウィンドウの最大長をスライドウィンドウの各段階ごとに順次表示しています.

  • この場合、3番目の長さから3番目の長さまでが最大長となり、6番目の長さまで保持されます.

  • 正解は3です.
    • コードで正解を探すプロセスを実現します.

  • まず、2つのポインタで問題を解き、両方のポインタは左から出発します.

  • それぞれ左側の起点から出発し、2番目のポインタ(ここではindex変数)は右側に拡張し続けます.

  • 既に存在する文字であれば、usedでは、この場合、最初のポインタstartをused[char]+1位置に更新する.
  • が表示されない最初の文字であれば、最大()部分の文字列の長さをチェックするたびに、より大きな値であれば更新されます.

  • 3番目のポジションからは、最低価格3を維持し続けます.
  • また、現在は文字の位置が更新されています.

  • 現在、used[Car]は現在の文字をキーとするハッシュテーブルであり、現在の位置を値として挿入します.
  • start = used[char] + 1は현재위치 + 1です.
    すでに表示されている文字の場合は、左ポインタstartを現在の位置に移動します.

  • しかし、すでに現れたと盲目的には言い難い.スライドウィンドウの外の文字は以前に現れたとしても、今は無視しなければならないからです.

  • したがって、比較文では、以下に示すように条件start <= used[char]が追加される.

  • これにより、スライドウィンドウ内の重複文字のみがTrue処理されます.
    • tanford cs193p Lecture 1 - lecture note
    Collection View Layout - MSPeekCollectionViewDelegateImplementation