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 * 1041 <= arr1[i], arr2[i] <= 108class Solution {
private int prefixLen = 0;
private class TrieNode{
TrieNode[] children;
boolean isWord;
TrieNode(){
children = new TrieNode[10];
isWord = true;
}
}
private class Trie{
TrieNode root;
Trie(){
root = new TrieNode();
}
void insert(int n){
TrieNode curr = root;
char[] cs = String.valueOf(n).toCharArray();
for(char c: cs){
int idx = c - '0';
if(curr.children[idx]==null)
curr.children[idx] = new TrieNode();
curr = curr.children[idx];
}
}
void longestPrefix(int n){
int count = 0;
TrieNode curr = root;
char[] cs = String.valueOf(n).toCharArray();
for(char c: cs){
int idx = c - '0';
if(curr.children[idx]==null)
break;
count++;
curr = curr.children[idx];
if(curr.isWord)
prefixLen = Math.max(prefixLen, count);
}
}
}
public int longestCommonPrefix(int[] arr1, int[] arr2) {
Trie trie = new Trie();
for(int i: arr1)
trie.insert(i);
for(int i: arr2)
trie.longestPrefix(i);
return prefixLen;
}
}