Find the Length of the Longest Common Prefix - Trie [JS]
Solution: Trie
Add each number (convert into string) from arr2
into a trie.
Go through each number in arr1
and iterate through the trie to find the longest matching prefix.
n = length of arr1 and arr2
, m = max length of arr1[i]/arr2[i]
Time Complexity: O(nm)
Space Complexity: O(nm)
var longestCommonPrefix = function(arr1, arr2) {
let trie = new Trie();
for (let num of arr2) {
let str = num.toString();
trie.add(str);
}
let longestCommonPrefix = 0;
for (let num of arr1) {
let str = num.toString();
let node = trie.root;
let matching = 0;
for (let char of str) {
node = node.children;
if (!node[char]) break;
matching++;
node = node[char];
}
longestCommonPrefix = Math.max(longestCommonPrefix, matching);
}
return longestCommonPrefix;
};
class TrieNode {
constructor() {
this.children = {};
this.count = 0;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
add(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
node = node.children;
let char = word[i];
if (!node[char]) node[char] = new TrieNode();
node = node[char];
node.count++;
}
}
}
Comments
Post a Comment