Find the Length of the Longest Common Prefix - Trie [JS]

Description 

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 arr2m = 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

Popular posts from this blog

Maximum Value of an Ordered Triplet II - Two Solutions [JS]

Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]

Sum of Prefix Scores of Strings - Trie [JS]

Maximum Count of Positive Integer and Negative Integer - Binary Search [JS]

Count Subarrays With Median K - Count Left & Right Balance [JS]