2 つの指定された文字列が互いに順列になるように、必要な操作の数を最小限に抑えます。

この記事では、指定された 2 つの文字列を互いに位置合わせするために必要な指定された操作の数を最小限に抑える方法について説明します。段階的なアプローチに従い、C コードの実装を提供します。問題と解決策を理解するのに役立つサンプル テスト ケースも提供します。

＃＃＃問題文＃＃＃

2 つの文字列 s1 と s2 が与えられた場合、s1 と s2 を互いに揃えるために必要な操作の最小数を見つける必要があります。 s1 の任意の 2 文字を交換するか、s2 の任意の 2 文字を交換するという 2 つの操作を実行できます。

方法と実装

この問題を解決するには、2 つの文字列内に存在しない文字の数、つまり 2 つの文字列内の文字の出現頻度の差をカウントする必要があります。どちらの文字列の文字も交換して等しくできるため、2 つの文字列を相互に並べ替えるのに必要な交換の最小数はこの回数の半分に等しくなります。

まず、2 つの配列を使用して 2 つの文字列内の文字の頻度を計算します。次に、2 つの配列を反復処理し、文字頻度間の絶対差を変数に追加します。この変数には、両方の文字列に存在しない文字の数が格納されます。

カウントを計算した後、2 つの文字列を相互に並べ替えるのに必要な最小スワップ数としてその半分を返します。

＃＃＃例＃＃＃

以下は、上記のメソッドの C コード実装です -

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

テストケースの例

このテスト ケースの文字列例として「hello」と「world」を考えてみましょう。

2 つの文字列の周波数配列は次のとおりです -

リーリー

文字「l」は s1 では頻度 2 で出現しますが、s2 では 1 のみ出現します。一方、文字「r」は s2 では頻度 1 で出現しますが、s1 には存在しません。したがって、両方の文字列に存在しない文字の数は 3 です。

したがって、2 つの文字列を互いに配置するために必要な交換の最小回数は 1 です。 s1 の「l」を s2 の「r」と交換すると、互いの順列である文字列「herlo」と「wold」を取得できます。

＃＃＃結論は＃＃＃

この記事では、2 つの指定された文字列を互いに位置合わせするために必要な指定された操作の数を最小限に抑える方法について説明しました。私たちは段階的なアプローチに従い、C コードの実装を提供しました。問題と解決策の理解に役立つサンプル テスト ケースも提供します。この問題は、時間計算量 O(n) と空間計算量 O(1) で解決できます。

以上が2 つの指定された文字列が互いに順列になるように、必要な操作の数を最小限に抑えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。