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

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

王林

リリース： 2023-09-10 14:41:02

転載

701 人が閲覧しました

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

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

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

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

＃＃＃例＃＃＃

入力

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

出力

– 2

イラスト

入力

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

出力

– 3

イラスト

このメソッドでは、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 の長さです。