JavaScript プログラムは文字列が相互に回転しているかどうかをチェックします

文字列の回転とは、2 つの文字列を右または左に回転して別の文字列を取得できることを意味します。文字列の右回転文字では、次のインデックスに移動し、文字列が円の中にあると仮定して、0 番目のインデックスについては、最後のインデックスの文字を取得します。左回転は右回転と似ていますが、方向が逆です。 2 つの文字列が与えられ、一方の文字列の文字を回転してもう一方の文字列を取得できるかどうかを判断する必要があります。

＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

説明: 最初の文字列を左に 2 回回転して、2 番目の文字列を取得できます。最初のループ後の String1 は「bcdefa」になり、次のループでは 2 番目の文字列と同じになります。

＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

説明 -

元の文字列を取得せずに文字列または配列を回転できる最大回転数は、指定された文字列または配列の長さに等しくなります。

ここでは、6 回回転しても文字列 1 から文字列 2 を取得できません。これは、最大回転回数を超えた後に 2 つの文字列を等しくすることが不可能であることを証明しています。

単純な方法

このメソッドでは、指定された文字列をその長さの回数だけ回転し、別の指定された文字列と照合します。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間と空間の複雑さ

上記のコードの時間計算量は O(N*N) です。ここで、N は指定された文字列のサイズです。

スペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

KMPアルゴリズム

このプログラムでは、KMP アルゴリズムを使用して回転を見つけます。コードに移りましょう。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

上記のプログラムの場合、時間と空間の計算量は両方とも O(N) です。 lps 配列に値を格納するために追加のスペースを使用します。

＃＃＃結論は＃＃＃

このチュートリアルでは、文字列の文字を左または右に回転することによって、指定された文字列を別の指定された文字列から取得できるかどうかを確認する JavaScript プログラムを実装しました。私たちは単純なアプローチを使用しました。これには、O(N*N) の時間計算量と O(1) の空間計算量が必要でした。さらに、時間と空間の複雑さが O(N) の KMP アルゴリズムを実装しました。

以上がJavaScript プログラムは文字列が相互に回転しているかどうかをチェックしますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。