毎日のアルゴリズム: 文字の繰り返しのない最長の部分文字列

[[421075]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

文字列が与えられた場合、重複する文字を含まない最長の部分文字列の長さを計算します。

例1:

入力: "abcabcbb"  
出力: 3
説明: 重複文字のない最長の部分文字列は「abc」なので、その長さは 3 です。

例2:

入力: "bbbbb"  
出力: 1
説明: 重複文字のない最長の部分文字列は「b」なので、その長さは 1 です。

例3:

入力: "pwwkew"  
出力: 3
説明: 重複文字のない最長の部分文字列は「wke」なので、その長さは 3 です。
     答えは部分文字列の長さでなければならないことに注意してください。 「pwke」は部分文字列ではなく、部分シーケンスです。

解決策1: アレイのメンテナンス

解決策: 配列を使用してスライディングウィンドウを維持する

文字列を走査し、文字がスライディングウィンドウ配列内にあるかどうかを判定する

そうでない場合は、配列にプッシュします
次に、スライディングウィンドウ配列内の同じ文字とその前の文字を削除し、現在の文字を配列にプッシュします。
次に、現在の最長部分文字列の長さにmaxを更新します。

トラバース後、最大値を返す

理解を助けるために絵を描きます:

コード実装:

 var lengthOfLongestSubstring =関数(s) {
    arr = []、 max = 0とします
( i = 0 とします; i < s.length; i++) {
        インデックス= arr.indexOf(s[i])とします。
        if(インデックス!== -1) {
            arr.splice(0,インデックス+1);
        }
        arr.push(s.charAt(i))
 max = Math. max (arr. length, max )
    }
戻る 最大 
 };

時間計算量: O(n2)。arr.indexOf() の時間計算量は O(n)、arr.splice(0, index+1) の時間計算量は O(n) です。

空間計算量: O(n)

解決策2: 下付き文字を維持する

解決策: スライディングウィンドウを維持するために下付き文字を使用する

コード実装:

 var lengthOfLongestSubstring =関数(s) {
    インデックス= 0、最大値= 0とします
(i = 0, j = 0; j < s.length; j++)の場合{
インデックス= s.substring (i, j).indexOf(s[j] )
        if(インデックス!== -1) {
            i = i +インデックス+ 1
        }
最大値= Math.max (最大値, j-i+1 )
    }
戻る 最大 
 };

時間計算量: O(n2)

空間計算量: O(n)

解決策3: 最適化されたマップ

解決：

マップを使用して、これまでに走査された文字を保存します。キーは文字で、値は添え字です。

i を使用して、繰り返しのない部分文字列の開始添え字をマークし、j は現在のトラバーサル文字の添え字です。

文字列をトラバースし、現在の文字がマップ内に既に存在するかどうかを判断します。存在する場合は、インデックス i で始まる非繰り返し部分文字列を、同じ文字の次の位置に更新します。この時点で、i から j までが最新の非繰り返し部分文字列であり、max を更新し、現在の文字とインデックスをマップに格納します。

最後に最大値を返す

コード実装:

 var lengthOfLongestSubstring =関数(s) {
    map = new Map()、 max = 0とします。
 (i = 0, j = 0; j < s.length; j++)の場合{
        （map.has(s[j])）の場合{
            i = Math.max (map.get(s[j]) + 1, i) です。
        }
最大値= Math.max (最大値, j-i+1 )
        マップをセットする(s[j], j)
    }
戻る 最大 
 };