2 つの文字列が相互に回転しているかどうかを効率的に判断するにはどうすればよいですか?

文字列のローテーションのチェック: 効率的なソリューション

ソフトウェア開発者のポジションの面接で、候補者は課題を突き付けられました。文字列は相互に回転されたバージョンです。具体的には、「s1」と「s2」が与えられた場合、その文字を回転させることで「s1」が「s2」の修正バージョンであるかどうかを検証することがタスクでした。

面接官のアプローチ

候補者の応答には、回転点を表す「s1」の部分文字列と一致する「s2」の最長のプレフィックスを見つけることが含まれていました。その時点で「s2」を「s2a」と「s2b」に分割することで、「s2a」と「s2b」の連結を「s1」と同等かどうか比較できます。

より簡単な解決策

しかし、インタビュアーは、より直接的なアプローチを提案しました。それは、「s1」と「s2」が同じ長さであることを確認してから、「s2」がそれ自体と連結された「s1」の部分文字列であるかどうかをテストするというものです。このメソッドは、回転された文字列が連結されると常に元の文字列の部分文字列になるという事実を利用します。

Java 実装

Java では、次の単純な実装が行われます。このソリューションは次のようになります。

<code class="java">boolean isRotation(String s1, String s2) {
    return (s1.length() == s2.length()) && ((s1 + s1).indexOf(s2) != -1);
}</code>

効率分析

このソリューションの時間計算量は O(n) です。n は文字列の長さです。単一の文字列の連結と、結合された結果に対する部分文字列の検索が含まれます。連結された文字列に必要なスペースのため、スペースの複雑さも O(n) です。

文字列のローテーションをチェックするための簡単で効率的な方法を提供することにより、この代替アプローチは、シンプルかつ効果的にというインタビュアーの要求を満たします。文字列の回転されたバージョンを検出します。

以上が2 つの文字列が相互に回転しているかどうかを効率的に判断するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。