文字列 A を追加して文字列 B を取得するために必要な最小限のサブシーケンスを追加します。

この問題では、str1 のサブシーケンスを使用して str2 を構築する必要があります。この問題を解決するには、str2 の最大長の部分文字列をカバーするような str1 の部分列を見つけることができます。ここでは、問題を解決する 2 つの異なる方法を学びます。

問題ステートメント – 長さの異なる 2 つの文字列 str1 と str2 が与えられています。次の条件に従って、str1 から str2 を構築する必要があります。

• str1 から任意のサブシーケンスを選択し、それを新しい文字列 (最初は空) に追加します。

str2 を構築するために必要なオペランドの最小数を返し、str2 を構築できない場合は -1 を出力する必要があります。

＃＃＃例＃＃＃

入力

– str1 = "acd"、str2 = "adc"

出力

– 2

イラスト

str1 の最初のサブシーケンスは「ad」です。したがって、文字列は「ad」になる可能性があります。
その後、str1 から "c" サブシーケンスを取得し、それを "ad" に追加して "adc" にします。

入力

– str1 = "adcb"、str2 = "abdca"

出力

– 3

イラスト

最初のサブシーケンスは str1 の「ab」です。
その後、「dc」文字列を取得でき、結果の文字列は「abdc」になります。
次に、「a」サブシーケンスを使用して、最終的な文字列「abdca」を生成します。
方法1

このメソッドでは、str1 を反復して複数のサブシーケンスを検索し、結果の文字列に追加します。

＃＃＃アルゴリズム＃＃＃

長さ 26 の「arr」配列を定義し、すべての要素を 0 に初期化して、文字の存在を str1 に格納します。

• str1 を繰り返し、文字の ASCII 値に従って配列要素の値を更新します

• 「last」変数を定義し、-1 で初期化して、最後にアクセスした要素を追跡します。さらに、操作回数を格納する変数「cnt」を定義し、0に初期化します。

• ループを使用して str2 を走査し始めます。

• 現在の文字が str1 にない場合は、-1 を返します。

• 「最後の 1」値を使用して「j」変数を初期化します。

• while ループを使用して、j の値が len 未満になり、str1[j] が文字

と等しくなるまで繰り返します。

• 「j」の値が「len」より大きい場合、「str1」を走査します。 「cnt」変数の値を増やし、「str1」を再度繰り返す必要があるため「last」を -1 に初期化し、現在の文字を再度考慮する必要があるため「I」の値を 1 減らします。使用を続けます。 「継続」キーワードを繰り返します。

• 「last」変数の値を「j」に更新します。

• ループのすべての反復が完了した後、「cnt 1」を返します。ここでは、最後の操作を考慮していないため、「cnt」に「1」を追加する必要があります。

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

  時間計算量 – O(N*M)、N は str2 の長さ、M は str1 の長さです。

動的空間を使用しないため、空間の複雑さ - O(1)。

方法 2

このメソッドでは、マッピングとコレクションのデータ構造を使用して、上記のメソッドの効率を向上させます。問題を解決するロジックは上記と同じです。

＃＃＃アルゴリズム＃＃＃

「chars_mp」を定義して、char ->sets{} をキーと値のペアとして保存します。

マッピングでは、str1 文字列に特定の文字が存在するインデックス セットを格納します。

「last」変数と「cnt」変数を定義する
str2 のトラバースを開始します。現在の文字インデックスを含むコレクションのサイズが 0 の場合、-1 が返されます。
現在の文字インデックス セットの「最後」の上限を見つけます。
上限が見つからない場合は、「cnt」の値を 1 つ増やし、「last」を -1 に設定し、「I」の値を 1 つ減らして、Continue キーワードを使用します。
「最後の」変数の値を更新します。
ループの反復が完了したら、「cnt」変数の値を返します

• p> ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

• 時間計算量

  – str2 を反復処理してループ内の「最後の」インデックスの上限を見つけるため、O(N*logN)。

• 空間複雑度

  – マップを使用して文字インデックスを保存するため、O(N)。

以上が文字列 A を追加して文字列 B を取得するために必要な最小限のサブシーケンスを追加します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。