Longest Substring Without Repeating Charctersのjavascript解法

1692 ワード

分析
この問題の最も理想的な状態は一回の文字列だけを巡回して、遍歴する時重複の文字があるかどうかを決定するために、私達は一つのハッシュテーブルhashの補助的なクエリが必要です.javascriptの中のオブジェクトはハッシュテーブルの役割として働くことができます.キーはある文字列の中の位置にある文字です.
巡回中に変数headがサブストリングの先頭を指し、変数tailがサブストリングの最後を指し、tailの位置を1つ後ろにシフトし、ハッシュテーブルでtailの位置にある新しい文字を照会し、hashの中に新しい文字があるかどうかで次のステップの動作を決定する.
想像してみると、私たちはtailを通して文字列を巡回しているので、tailの更新方式は毎回文字列が巡回されるまで+1である.同時に、hashの更新については、文字を巡回する過程で、hashに新しい{ : }を追加したり、既存の文字の位置をカバーしたりします.headはどうやってその値を更新しますか?headの値は、headが新しい文字を巡回したときにtailに既に存在しているかどうかによって決定される.
  • が存在しない場合、現在の部分列は重複文字のない部分列であることを示し、hashの位置は変動する必要がない.
  • が存在する場合、headにおける重複文字の文字列内の位置と現在のhashの位置との相対位置関係で処理する.
  • 重複文字はheadの前に位置し、headの値は更新する必要がない
  • である.
  • 重複文字はheadheadの間にあり、tailの値は重複文字に更新された次のビット
  • である.
    最後に、サブストリングの最大長さheadについては、その値は明らかにcountであり、文字を巡回するたびに更新すればよい.
    答えを出す
    コードは以下の通りです
    var lengthOfLongestSubstring = function(s) {
        if ( Object.prototype.toString.call(s) !== "[object String]" ) return;
    
        var head = 0,
            tail = 0,
            len = s.length,
            count = 0,
            hash = {};
    
        for ( ;tail < len; tail ++ ) {
            if (hash[s.charAt(tail)] !== undefined) {
                head = Math.max(hash[s.charAt(tail)] + 1, head);
            }
            count = Math.max(count, tail - head + 1);
            hash[s.charAt(tail)] = tail;
        }
    
        return count;
    };