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
の値は更新する必要がないhead
とhead
の間にあり、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;
};