特定の文字列を形成するために必要なプレフィックスとサフィックスの最小数

プレフィックスは、指定された文字列内の、0 番目のインデックスから始まり文字列のサイズまでの部分文字列です。同様に、サフィックスは、長さ 1 から文字列のサイズまでの、最後のインデックスで終わる任意の部分文字列です。 2 つの文字列が与えられます。最初の文字列は、2 番目の文字列の任意の数のプレフィックスとサフィックスを使用して、何らかの方法で作成する必要があります。指定された文字列を指定されたメソッドから作成できない場合は、-1 を返します。

＃＃＃例＃＃＃ リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

接頭辞「points」と接尾辞「tutorial」を使用し、それらを連結することで最初の文字列を取得できます。これには 2 つの部分文字列のみが必要で、これが私たちの答えまたは出力です。

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

2 番目の文字列の指定されたサフィックスまたはプレフィックスから最初の文字列を取得できません。

＃＃＃方法＃＃＃

この問題を解決するために、動的プログラミングの概念を使用します。これは、すでに発生したインスタンスを保存することで解決されます。

まず、2 つの文字列をパラメータとして受け取り、整数を返す関数を作成します。

• この関数では、まず文字列の長さを取得し、プレフィックスを取得するためのハッシュ セットと一時文字列を作成します。

• 2 番目の文字列を反復処理して、すべてのプレフィックスを取得し、ハッシュ セットに保存します。同様に、文字列を後ろから前にたどることで、すべてのサフィックスを取得し、ハッシュ セットに保存できます。

• 次に、動的プログラミングの結果を格納する配列を作成し、配列の各インデックス位置に -1 を格納します。

• ネストされた for ループを使用して、最初の文字列をチャンクに分割し、ハッシュ マップ内のすべてのチャンクを連結できるかどうかを確認します。

• 必要な部分文字列の数を減らすために最善を尽くしますが、それが不可能な場合は、-1 が返されます。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
  時間と空間の複雑さ

取得したすべてのサフィックスの複雑さが高いため、上記のコードの時間計算量は O(N^2) ですが、文字列を逆にすることで時間計算量を減らすことができます。さらに、文字列をハッシュ セットに格納して時間の複雑さを高め、動的プログラミングのためにループをネストします。

すべてのサフィックスとプレフィックスをハッシュ マップに保存しているため、上記のコードの空間複雑さは O(N^2) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、指定された文字列のサフィックスとプレフィックス内の部分文字列の最小数を見つけて、別の指定された文字列を作成するコードを実装しました。それが不可能な場合は、-1 を出力します。要素をハッシュ セットに格納し、時間と空間の複雑さが O(N^2) の入れ子になったループを使用することで、動的プログラミングの概念を使用しました。

以上が特定の文字列を形成するために必要なプレフィックスとサフィックスの最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。