JavaScript で非反復部分文字列を検索する方法

実際の開発では、文字列に対していくつかの操作や処理を実行する必要があることがよくあります。その 1 つは、反復しない部分文字列を見つけることです。たとえば、文字列「abcabcbb」では、最長の非反復部分文字列は「abc」であり、文字列「bbbbbb」では、最長の非反復部分文字列は「b」です。これらの問題は、アルゴリズムでは「最長の非反復部分文字列」問題として知られており、JavaScript を使用して解決できます。

1. 暴力的な列挙方法

最も単純な方法は、総当たりの列挙方法を使用することです。繰り返しの文字が現れるまで。次に、この時点での部分文字列の長さを記録し、部分文字列をリセットし、トラバーサルが終了するまで文字列を下方向にトラバースし続けます。

コードは次のとおりです:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  for(let i = 0; i < str.length; i++) {
    let map = new Map(); // 定义 Map 来保存子串中元素出现的次数
    let length = 0; // 定义子串长度为 0
    for(let j = i; j < str.length; j++) {
      if(map.has(str[j])) { // 如果子串中已经有这个元素了
        maxLength = Math.max(maxLength, length); // 更新最大长度
        break; // 说明这个子串已经不符合要求了，跳出内部循环
      } else {
        map.set(str[j], 1); // 在 Map 中记录该元素的出现次数
        length++; // 子串长度 +1
        maxLength = Math.max(maxLength, length); // 更新最大长度
      }
    }
  }
  return maxLength;
}

このメソッドの時間計算量は O(n^3) です。ネストされたループの数が非常に多いため、処理が長くなると効率的ではありません弦は非常に低いです。

2. スライディング ウィンドウ方式

効率を向上させるために、スライディング ウィンドウ方式を使用できます。スライディング ウィンドウの考え方は、長さ k のウィンドウを維持し、このウィンドウをスライドさせて文字列を処理することです。この問題では、スライディング ウィンドウの長さが非反復文字列の長さになります。

具体的には、文字列をトラバースするときに、開始ポインターとエンドポインターを定義し、これら 2 つのポインターがウィンドウを形成します。各ループで、終了ポインターが指す要素がウィンドウに存在しない場合は、それをウィンドウに追加し、ウィンドウを拡張してウィンドウの長さを更新できます。終了ポインタが指す要素がウィンドウ内にすでに存在する場合は、開始ポインタを右に移動し、終了ポインタが指す要素がウィンドウ内に存在しなくなるまでウィンドウを縮小する必要があります。このプロセスでは、マッピング テーブルを使用して、ウィンドウ内の各要素の出現数を記録する必要があります。

コードは次のとおりです:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  let map = new Map(); // 定义 Map 来保存元素出现的次数
  let left = 0; // 定义左指针为 0
  for(let right = 0; right < str.length; right++) {
    if(map.has(str[right])) { // 如果窗口内已经有该元素了
      left = Math.max(left, map.get(str[right]) + 1); // 更新左指针，向右移动
    }
    map.set(str[right], right); // 在 Map 中记录该元素的位置
    maxLength = Math.max(maxLength, right - left + 1); // 更新最大长度
  }
  return maxLength;
}

スライディング ウィンドウ メソッドの時間計算量は O(n) です。HashMap を使用して文字をすばやく見つけて保存します。これは、スライディング ウィンドウ メソッドよりも高速かつ効率的です。ブルートフォース列挙法。

3. 概要

文字列内の最長の非反復部分文字列の問題については、総当たり列挙法とスライディング ウィンドウ法という 2 つの方法を使用して解決できます。ブルート フォース列挙法は時間の複雑さが高くなりますが、スライディング ウィンドウ法はより効率的です。実際の開発では、必要に応じて問題を解決するための適切な方法を選択できます。

以上がJavaScript で非反復部分文字列を検索する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。