Solving Algorithmic Problems

Description   Solution: Trie Add each word (right-to-left) from  wordsContainer  into a trie. Each trie node keeps track of the index of the smallest lengthed word sharing this suffix. This way, we don't need to traverse the whole trie to find all the words and decide the index. For each word query, Go through each character from right-to-left, and find the longest matching path in the trie. Since each trie node is pre-populated with the index we need, we just use  node.index n = sum(wordsContainer[i].length) ,  m = sum(wordsQuery[i].length) Time Complexity:  O(n + m) Space Complexity:  O(n) var stringIndices = function ( wordsContainer, wordsQuery ) { let n = wordsContainer.length, trie = new TrieNode(), defaultIndex = 0 ; for ( let i = 0 ; i < n; i++) { let word = wordsContainer[i], node = trie; for ( let j = word.length - 1 ; j >= 0 ; j--) { node = node.children; let char = word[j]; if (!node[char]) node...

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 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 ; } } clas...

Description   Solution: Trie Keep track of two pointers  l  and  r  as the left and right pointers of the current valid substring in word. Add all the forbidden words into a trie. Iterate through each index  l  from right to left. From each index  l , Iterate through the trie while we have matching nodes. Once we find the first forbidden word in the trie, update the right pointer to be  i - 1 . The advantage of using is trie is that we don't have to create a substring for each iteration, resulting in a  O(k^2)  time complexity. Using a trie will only be  O(k)  per index  l . n = length of word ,  m = length of forbidden ,  k = max(forbidden[i].length) Time Complexity:  O(n * k + mk) Space Complexity:  O(mk) var longestValidSubstring = function ( word, forbidden ) { let n = word.length, trie = new Trie(); for ( let i = 0 ; i < forbidden.length; i++) { trie.add(forbidden[i]); } le...