指定されたサイズのバイナリ文字列配列に存在しない順列を検索します

この問題では、配列から長さ N の欠落しているバイナリ文字列をすべて見つける必要があります。この問題は、長さ N のバイナリ文字列のすべての順列を見つけて、配列内にどの順列が存在しないかをチェックすることで解決できます。ここでは、この問題を解決するための反復的および再帰的方法を見ていきます。

問題ステートメント - 異なる長さのバイナリ文字列を含む長さ N の配列 arr[] が与えられました。配列から長さ N の欠落しているバイナリ文字列をすべて見つける必要があります。

例例

入力 – arr = {"111", "001", "100", "110"}, N = 3

出力 – [000, 010, 011, 101]

説明 – 2 の 3 乗は 8 に等しいため、長さ 3 のバイナリ文字列が 8 つあります。したがって、不足している長さ 3 の 4 つのバイナリ文字列が出力されます。

入力 – str = {‘00’, ‘10’, ‘11’}, N = 2

出力 –['01']

説明 – 「01」が配列にないため、出力に表示されます。

方法 1

ここでは、反復法を使用して、長さ N の可能なバイナリ文字列をすべて見つけます。その後、文字列が配列内に存在するかどうかを確認します。存在しない場合は、文字列を出力します。

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

コレクションを定義し、insert() メソッドを使用して、配列内のすべての文字列をコレクションに追加します。
total 変数を 2N で初期化します。2N は長さ N

• の文字列の総数です。

変数 'c​​nt' を定義し、それをゼロに初期化して、欠落している組み合わせの総数を保存します。
ループを使用して「合計」回数反復し、長さ N のバイナリ文字列をすべて検索します。
ループ内で、「num」文字列変数を空の文字列で初期化します。
ネストされたループを合計 N 回繰り返し使用し、最後の繰り返しから開始して長さ N の文字列を作成します。
find() メソッドを使用して、コレクションに現在の文字列が含まれているかどうかを確認します。その場合は、「cnt」の値を 1 増やします。
文字列がマップにない場合は、出力に表示されるように印刷します
「cnt」の値が合計数と等しい場合は、長さ N の文字列がすべて配列内に存在することを意味し、「-1」が出力されます。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
時間計算量 - O(N*2N)。O(N) は文字列が配列内に存在するかどうかを確認するために使用され、O(2N) はすべての可能な順列を見つけるために使用されます。

文字列の格納に set を使用するため、空間複雑度 - O(N)。

方法 2

このアプローチでは、長さ N のすべての可能なバイナリ文字列を見つけるための再帰的アプローチの使用を示します。

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

コレクションを定義し、すべての配列値をコレクションに挿入します。

generateCombinations() 関数を呼び出してバイナリ文字列のすべての組み合わせを生成します

• generateCombinations() 関数で基本ケースを定義します。インデックスが N に等しい場合、currentCombination がリストに追加されます。

• 現在の組み合わせに「0」または「1」を追加した後、generateCombinations() 関数を再帰的に呼び出します。
すべての組み合わせを取得した後、配列内にどの組み合わせが存在し、どの組み合わせが存在しないかを確認します。また、不足している組み合わせを出力して出力に表示します。

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

  時間計算量 - O(N*2N)
すべての組み合わせを配列に格納するため、空間複雑度 - O(2N)。

• どちらの方法も同じロジックを使用して問題を解決します。最初の方法では、反復手法を使用して長さ N のバイナリ文字列のすべての組み合わせを検索します。これは、2 番目の方法で使用される再帰的手法よりも高速です。また、2 番目の方法は最初の方法よりも多くのスペースを消費します。

以上が指定されたサイズのバイナリ文字列配列に存在しない順列を検索しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。