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:
範例2:
約束:
提示:
解:
我們可以利用 HashSet 來儲存一個陣列中的前綴,然後檢查第二個陣列中的這些前綴。
產生前綴:對於arr1和arr2中的每個數字,產生所有可能的前綴。前綴由最左邊的數字開始的一位或多位數字組成。
將 arr1 的前綴儲存在集合中:使用 HashSet 儲存 arr1 中所有數字的前綴,可以確保在檢查 arr2 中的前綴時快速找到。
找出最長公共前綴:對於 arr2 中的每個數字,產生其前綴,並檢查步驟 2 中的 HashSet 中是否存在這些前綴。追蹤找到的最長前綴。
傳回最長公共前綴的長度:如果找到公共前綴,則傳回其長度;否則,傳回 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 ?>
雜湊集建立:
前綴檢查:
回傳結果:
此解決方案非常高效,並且在所提供的限制內運作良好。
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
以上是求最長公共前綴的長度的詳細內容。更多資訊請關注PHP中文網其他相關文章!