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:
Input: arr1 = [1,10,100], arr2 = [1000] Output: 3 Explanation: There are 3 pairs (arr1[i], arr2[j]): - The longest common prefix of (1, 1000) is 1. - The longest common prefix of (10, 1000) is 10. - The longest common prefix of (100, 1000) is 100. The longest common prefix is 100 with a length of 3.
Example 2:
Input: arr1 = [1,2,3], arr2 = [4,4,4] Output: 0 Explanation: There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0. Note that common prefixes between elements of the same array do not count.
Constraints:
1 <= arr1.length, arr2.length <= 5 * 104
1 <= arr1[i], arr2[i] <= 108
Approach 01:
-
C++
-
Python
#include <iostream> #include <memory> #include <vector> #include <string> using namespace std; struct TrieNode { vector<shared_ptr<TrieNode>> children; TrieNode() : children(10) {} // Initializes children for digits 0-9 }; class Trie { public: // Insert a number string into the Trie void insert(const string& numberString) { shared_ptr<TrieNode> currentNode = root; for (const char digit : numberString) { const int index = digit - '0'; // Convert character to corresponding index if (currentNode->children[index] == nullptr) currentNode->children[index] = make_shared<TrieNode>(); currentNode = currentNode->children[index]; } } // Search for the longest common prefix of a number string int search(const string& numberString) { int commonPrefixLength = 0; shared_ptr<TrieNode> currentNode = root; for (const char digit : numberString) { const int index = digit - '0'; if (currentNode->children[index] == nullptr) break; currentNode = currentNode->children[index]; ++commonPrefixLength; } return commonPrefixLength; } private: shared_ptr<TrieNode> root = make_shared<TrieNode>(); // Root of the Trie }; class Solution { public: // Function to find the longest common prefix between two arrays of integers int longestCommonPrefix(vector<int>& array1, vector<int>& array2) { int maxPrefixLength = 0; Trie trie; // Insert all numbers from array1 into the Trie for (const int number : array1) trie.insert(to_string(number)); // Search for the longest common prefix with numbers in array2 for (const int number : array2) maxPrefixLength = max(maxPrefixLength, trie.search(to_string(number))); return maxPrefixLength; } };
class TrieNode: def __init__(self): # Initializes children for digits 0-9 self.children = [None] * 10 class Trie: def __init__(self): # Root of the Trie self.root = TrieNode() # Insert a number string into the Trie def insert(self, numberString): currentNode = self.root for digit in numberString: index = ord(digit) - ord('0') # Convert character to corresponding index if currentNode.children[index] is None: currentNode.children[index] = TrieNode() currentNode = currentNode.children[index] # Search for the longest common prefix of a number string def search(self, numberString): commonPrefixLength = 0 currentNode = self.root for digit in numberString: index = ord(digit) - ord('0') if currentNode.children[index] is None: break currentNode = currentNode.children[index] commonPrefixLength += 1 return commonPrefixLength class Solution: # Function to find the longest common prefix between two arrays of integers def longestCommonPrefix(self, array1: List[int], array2: List[int]) -> int: maxPrefixLength = 0 trie = Trie() # Insert all numbers from array1 into the Trie for number in array1: trie.insert(str(number)) # Search for the longest common prefix with numbers in array2 for number in array2: maxPrefixLength = max(maxPrefixLength, trie.search(str(number))) return maxPrefixLength
Time Complexity
- Inserting into the Trie:
Each number from
array1
is converted to a string and inserted into the Trie. For a number with \(d\) digits, insertion takes \(O(d)\), where \(d\) is the number of digits in the number. If the size ofarray1
is \(n_1\) and the maximum number of digits in a number is \(d_{\text{max}}\), then inserting all numbers takes \(O(n_1 \cdot d_{\text{max}})\). - Searching the Trie:
For each number in
array2
, we search for the longest common prefix. Similar to insertion, searching takes \(O(d)\) for a number with \(d\) digits. If the size ofarray2
is \(n_2\) and the maximum number of digits in a number is \(d_{\text{max}}\), then searching for all numbers takes \(O(n_2 \cdot d_{\text{max}})\). - Overall Time Complexity:
The overall time complexity is \(O((n_1 + n_2) \cdot d_{\text{max}})\), where:
- \(n_1\) is the number of elements in
array1
- \(n_2\) is the number of elements in
array2
- \(d_{\text{max}}\) is the maximum number of digits in the numbers from both arrays.
- \(n_1\) is the number of elements in
Space Complexity
- Trie Node Storage:
The Trie stores digits (0-9), so each node has 10 children pointers. For each number, we store up to \(d_{\text{max}}\) nodes. In the worst case, where all numbers from
array1
are unique, we will have \(O(n_1 \cdot d_{\text{max}})\) nodes in the Trie. - Auxiliary Space:
We also use space for storing the
Trie
structure, along with a string conversion for each number (which takes \(O(d_{\text{max}})\) space for each number during insertion and search). - Overall Space Complexity:
The space complexity is \(O(n_1 \cdot d_{\text{max}})\), primarily due to storing the Trie nodes, where \(n_1\) is the number of elements in
array1
and \(d_{\text{max}}\) is the maximum number of digits in the numbers.