文字列間の文字を何度でも置き換えることにより、指定された文字列を T に変換します。

文字列の変換とは、指定された条件に基づいて、指定された文字列と同じにする必要があることを意味します。この質問では、文字列「arr」とサイズ「M」の文字列「T」で構成される配列が与えられています。私たちのタスクは、配列の文字列 ( arr[i] ) から任意の文字を削除し、その文字を別の文字列の任意のインデックスに挿入することによって、配列内に存在するすべての文字列を指定された文字列と同一にできるかどうかを確認することです。 String T A string同じ配列 ( arr[j] ) の。これは何度でも行うことができます。配列内のすべての文字列を文字列 'T' と同一にできる場合は「YES」を返し、それ以外の場合は「NO」を返します。

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

イラスト

配列内のすべての文字列を文字列 T と同一にする可能な方法の 1 つは次のとおりです -

文字列 arr[1] ("wxxy") のインデックス 2 の文字を削除し、文字列 arr[2] ("wyzz") のインデックス 1 に挿入します。その場合、次のようになります: ["wxyz","wxy","wxyzz"]
文字列 arr[2] ("wxyzz") のインデックス 3 の文字を削除し、文字列 arr[1] ("wxy") のインデックス 3 に挿入します。すると、["wxyz","wxyz","wxyz"] のようになります。
上記の手順を実行した後、配列内のすべての文字列を文字列 T と同じにすることができます。したがって、答えは「YES」です。

リーリー リーリー

イラスト

配列には 3 つの文字列があり、そのうち 2 つは文字列 T と同じですが、インデックス番号 1 の文字列は異なります。文字列 T の一部ではないさまざまな文字が含まれています。配列内のすべての文字列を文字列 T にすることはできません。したがって、答えは「NO」です。

方法: ハッシュマップを使用する

上記で指定された文字列の例を見てきました。メソッド -

に移りましょう。

次の 2 つの観察結果があります -

配列内のすべての文字列を文字列 T と同じにする必要があるため、配列内の各文字列のすべての文字が文字列 T に出現する必要があります。言い換えれば、異なるキャラクターは存在しません。そうしないと条件を満たせません。
配列内のすべての文字列の文字の出現頻度を計算した後、各文字の出現頻度は配列 "N" のサイズと等しくなる必要があります。

• 上記の観察に基づいて、確認する必要がある条件が 2 つあります。

サイズ配列「freqArr」の文字列のハッシュ マップは、文字列「T」のハッシュ マップ「freqT」と等しくなります。として ＃＃＃＃＃＃
• リーリー

文字列 T のすべての文字は、配列内のすべての文字列に出現する必要があります。文字列 T の各文字は、配列文字列内で「N」の頻度カウントを持つ必要があります。として-＃＃＃＃＃＃

リーリー

配列 string と string T 内の文字の頻度を計算する必要があるため、ハッシュを使用してこの問題を解決できます。
• ＃＃＃例＃＃＃

  理解を深めるために、上記のメソッドのコードを見てみましょう -

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

時間と空間の複雑さ

上記のコードの時間計算量は O(M N*L)

上記のコードの空間計算量は O(M)

です。

ここで、M は文字列 T のサイズ、N は配列のサイズ、L は配列内に存在する最長の文字列です。

＃＃＃結論は＃＃＃

このチュートリアルでは、文字列間の文字を必要な回数だけ置き換えることによって、指定された文字列を T に変換するプログラムを実装しました。周波数を保存する必要があったため、ハッシュ方式を実装しました。このメソッドでは主に 2 つの条件をチェックします。すべての条件が満たされた場合、配列内のすべての文字列を文字列 T と同じ文字列に変換できたことを意味します。

以上が文字列間の文字を何度でも置き換えることにより、指定された文字列を T に変換します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。