最長の共通プレフィックスの長さを求める

3043。最長の共通プレフィックスの長さを求める

難易度: 中

トピック: 配列、ハッシュ テーブル、文字列、トライ

正の整数 arr1 と arr2 を持つ 2 つの配列が与えられます。

正の整数の 接頭辞 は、左端 の桁から始まる 1 つ以上の桁で形成される整数です。たとえば、123 は整数 12345 の接頭辞ですが、234 は ではありません.

共通接頭辞 は整数 c であり、c は a と b の両方の接頭辞になります。たとえば、5655359 と 56554 には共通のプレフィックス 565 がありますが、1223 と 43456 には共通のプレフィックスがありません。 x が arr1 に属し、y が arr2 に属するような、整数のすべてのペア (x, y) の間で

の長さを見つける必要があります。 すべてのペアの

の共通プレフィックスの長さを返します。それらの間に共通のプレフィックスが存在しない場合は、0. を返します。

入力:
• arr1 = [1,10,100]、arr2 = [1000]
出力:
• 3
説明:
• 3 つのペア (arr1[i]、arr2[j]) があります。 (1, 1000) の最も長い共通プレフィックスは 1 です。
  • (10, 1000) の最も長い共通プレフィックスは 10 です。
  • (100, 1000) の最も長い共通プレフィックスは 100 です。
  • 最も長い共通プレフィックスは 100、長さは 3 です。

入力:
• arr1 = [1,2,3]、arr2 = [4,4,4]
出力:
• 4
説明:
• どのペア (arr1[i]、arr2[j]) にも共通のプレフィックスが存在しないため、0 を返します。 同じ配列の要素間の共通の接頭辞はカウントされないことに注意してください。

1. arr2 の各要素のすべての可能なプレフィックスについて、それが HashSet に存在するかどうかを確認します。

HashSet を利用して 1 つの配列からプレフィックスを保存し、2 番目の配列でそれらのプレフィックスをチェックできます。

アプローチ：

1. プレフィックスの生成

   : arr1 と arr2 の各数値に対して、可能なすべてのプレフィックスを生成します。プレフィックスは、左端の数字から始まる 1 つ以上の数字で形成されます。

2. arr1 のプレフィックスをセットに保存する

   : HashSet を使用して数値のすべてのプレフィックスを arr1 に保存すると、arr2 からのプレフィックスをチェックするときに高速な検索が保証されます。

3. 最長の共通プレフィックスの検索

   : arr2 の各番号について、そのプレフィックスを生成し、これらのプレフィックスのいずれかが手順 2 の HashSet に存在するかどうかを確認します。見つかった最長のプレフィックスを追跡します。

4. 最長の共通プレフィックスの長さを返す

   : 共通プレフィックスが見つかった場合は、その長さを返します。それ以外の場合は 0 を返します。

このソリューションを PHP で実装してみましょう:

<?php
/**
 * @param Integer[] $arr1
 * @param Integer[] $arr2
 * @return Integer
 */
function longestCommonPrefix($arr1, $arr2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$arr1 = [1, 10, 100];
$arr2 = [1000];
echo longestCommonPrefix($arr1, $arr2); // Output: 3

$arr1 = [1, 2, 3];
$arr2 = [4, 4, 4];
echo longestCommonPrefix($arr1, $arr2); // Output: 0
?>

1. ハッシュセットの作成

   :

   最初に連想配列 $prefixSet を作成し、arr1 内の数値の可能なすべての接頭辞を保持します。
   • arr1 内の各数値を反復処理し、文字列に変換し、substr 関数を使用してそのすべてのプレフィックスを抽出します。各プレフィックスは $prefixSet に保存されます。
2. プレフィックスチェック

   :

   次に、arr2 内の各数値をループし、同様に文字列に変換します。
   • arr2 の各数値について、考えられるすべてのプレフィックスを再度抽出します。
   • $prefixSet にプレフィックスが存在する場合、その長さが現在見つかっている最大長 ($maxLength) より大きいかどうかを確認します。
3. 結果を返す

   :

   最後に、見つかった最も長い共通プレフィックスの長さを返します。
複雑：

時間計算量
• : O(n * m) ここで、n と m はそれぞれ arr1 と arr2 の長さです。これは、すべての数値とそのプレフィックスを処理しているためです。
空間複雑度
• : O(p) ここで、p は HashSet に格納されているプレフィックスの総数です。
このソリューションは効率的であり、指定された制約内でうまく機能します。

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

以上が最長の共通プレフィックスの長さを求めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。