가장 긴 공통 접두사의 길이 찾기-PHP 튜토리얼-php.cn

가장 긴 공통 접두사의 길이 찾기

Susan Sarandon

풀어 주다： 2024-09-24 22:15:14

원래의

342명이 탐색했습니다.

Find the Length of the Longest Common Prefix

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

難易度: 中

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

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

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

2 つの整数 a と b の

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

最長の共通プレフィックス

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

最長

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

例 1:

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

例 2:

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

制約:

1 4

1 8

ヒント:

arr1 の各要素の可能なプレフィックスをすべて HashSet に入れます。

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

解決策:

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

アプローチ：

プレフィックスの生成
: arr1 と arr2 の各数値に対して、可能なすべてのプレフィックスを生成します。プレフィックスは、左端の数字から始まる 1 つ以上の数字で形成されます。
arr1 のプレフィックスをセットに保存する
: HashSet を使用して数値のすべてのプレフィックスを arr1 に保存すると、arr2 からのプレフィックスをチェックするときに高速な検索が保証されます。
最長の共通プレフィックスの検索
: arr2 の各番号について、そのプレフィックスを生成し、これらのプレフィックスのいずれかが手順 2 の HashSet に存在するかどうかを確認します。見つかった最長のプレフィックスを追跡します。
最長の共通プレフィックスの長さを返す
: 共通プレフィックスが見つかった場合は、その長さを返します。それ以外の場合は 0 を返します。

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

説明：

<?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
?>

로그인 후 복사

ハッシュセットの作成
:
最初に連想配列 $prefixSet を作成し、arr1 内の数値の可能なすべての接頭辞を保持します。
- arr1 内の各数値を反復処理し、文字列に変換し、substr 関数を使用してそのすべてのプレフィックスを抽出します。各プレフィックスは $prefixSet に保存されます。
プレフィックスチェック
:
次に、arr2 内の各数値をループし、同様に文字列に変換します。
- arr2 の各数値について、考えられるすべてのプレフィックスを再度抽出します。
- $prefixSet にプレフィックスが存在する場合、その長さが現在見つかっている最大長 ($maxLength) より大きいかどうかを確認します。
結果を返す
:
最後に、見つかった最も長い共通プレフィックスの長さを返します。