Home > Article > Backend Development > Find the Length of the Longest Common Prefix
3043. Find the Length of the Longest Common Prefix
Difficulty: Medium
Topics: Array, Hash Table, String, Trie
You are given two arrays with positive integers arr1 and arr2.
A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.
A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565 while 1223 and 43456 do not have a common prefix.
You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.
Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.
Example 1:
Example 2:
Constraints:
Hint:
Solution:
We can utilize a HashSet to store the prefixes from one array and then check for those prefixes in the second array.
Generate Prefixes: For each number in arr1 and arr2, generate all possible prefixes. A prefix is formed by one or more digits starting from the leftmost digit.
Store Prefixes of arr1 in a Set: Using a HashSet to store all prefixes of numbers in arr1 ensures fast lookups when checking prefixes from arr2.
Find Longest Common Prefix: For each number in arr2, generate its prefixes and check if any of these prefixes exist in the HashSet from step 2. Track the longest prefix found.
Return the Length of the Longest Common Prefix: If a common prefix is found, return its length; otherwise, return 0.
Let's implement this solution in PHP: 3043. Find the Length of the Longest Common Prefix
Explanation:
HashSet Creation:
- We first create an associative array $prefixSet to hold all possible prefixes of numbers in arr1.
- We iterate through each number in arr1, convert it to a string, and extract all its prefixes using the substr function. Each prefix is stored in the $prefixSet.
Prefix Checking:
- Next, we loop through each number in arr2, converting it to a string as well.
- For each number in arr2, we again extract all possible prefixes.
- If a prefix exists in $prefixSet, we check if its length is greater than the current maximum length found ($maxLength).
Return the Result:
- Finally, we return the length of the longest common prefix found.
Complexity:
This solution is efficient and works well within the provided constraints.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
The above is the detailed content of Find the Length of the Longest Common Prefix. For more information, please follow other related articles on the PHP Chinese website!