首頁  >  文章  >  後端開發  >  求最長公共前綴的長度

求最長公共前綴的長度

Susan Sarandon
Susan Sarandon原創
2024-09-24 22:15:14412瀏覽

Find the Length of the Longest Common Prefix

3043。求最長公字前綴的長度

難度:

主題:陣列、雜湊表、字串、Trie

給你兩個數組,其中整數arr1和arr2。

正整數的前綴是由一個或多個數字組成的整數,從其最左邊數字開始。例如,123是整數12345的前綴,而234是不是

兩個整數 a 和 b 的

A 共同前綴 是一個整數 c,使得 c 是 a 和 b 的前綴。例如,5655359 和 56554 有一個共同的前綴 565,而 1223 和 43456 沒有 有共同的前綴。

您需要找出所有整數對 (x, y) 之間的 最長公共前綴 的長度,使得 x 屬於 arr1,y 屬於 arr2。

回傳所有對中最長公共前綴的長度。如果它們之間不存在公共前綴,則傳回 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

提示:

  1. 將arr1中每個元素所有可能的前綴放入一個HashSet中。
  2. 對於arr2中每個元素的所有可能的前綴,檢查它是否存在於HashSet中。

解:

我們可以利用 HashSet 來儲存一個陣列中的前綴,然後檢查第二個陣列中的這些前綴。

方法:

  1. 產生前綴:對於arr1和arr2中的每個數字,產生所有可能的前綴。前綴由最左邊的數字開始的一位或多位數字組成。

  2. 將 arr1 的前綴儲存在集合中:使用 HashSet 儲存 arr1 中所有數字的前綴,可以確保在檢查 arr2 中的前綴時快速找到。

  3. 找出最長公共前綴:對於 arr2 中的每個數字,產生其前綴,並檢查步驟 2 中的 HashSet 中是否存在這些前綴。追蹤找到的最長前綴。

  4. 傳回最長公共前綴的長度:如果找到公共前綴,則傳回其長度;否則,傳回 0。

讓我們用 PHP 實作這個解: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
?>

解釋:

  1. 雜湊集建立:

    • 我們先建立一個關聯陣列 $prefixSet 來保存 arr1 中所有可能的數字前綴。
    • 我們迭代 arr1 中的每個數字,將其轉換為字串,並使用 substr 函數提取其所有前綴。每個前綴都儲存在 $prefixSet 中。
  2. 前綴檢查:

    • 接下來,我們循環遍歷 arr2 中的每個數字,並將其轉換為字串。
    • 對於 arr2 中的每個數字,我們再次提取所有可能的前綴。
    • 如果 $prefixSet 中存在前綴,我們檢查其長度是否大於目前找到的最大長度 ($maxLength)。
  3. 回傳結果:

    • 最後,我們返回找到的最長公共前綴的長度。

複雜:

  • 時間複雜度:O(n * m),其中n和m分別是arr1和arr2的長度。這是因為我們正在處理每個數字及其前綴。
  • 空間複雜度:O(p),其中p是儲存在HashSet中的前綴總數。

此解決方案非常高效,並且在所提供的限制內運作良好。

聯絡連結

如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!

如果您想要更多類似的有用內容,請隨時關注我:

  • 領英
  • GitHub

以上是求最長公共前綴的長度的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn