JS | Auto-complete feature using Trie | Search Suggestions System | Coding Round Interview Question

Input: 
products = ["mobile","mouse","moneypot","monitor","mousepad"],
searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

The idea,

  • Sorting Simple Traversal
  • Trie + DFS

Sort | Simple Traversal

  1. Sort the products
  2. Keep filtering products that match our input
var suggestedProductsSort = function(products, searchWord) {
products.sort();
let res = [];
for (let i=0; i< searchWord.length; i++) {
products = products.filter( (p) => p[i] == searchWord[i]);
res.push(products.slice(0, 3));
}
return res;
}

Trie + DFS

  1. Create a Trie from the given products input.
  2. Iterate each character of the searchWord adding it to the prefix to search for.
  3. After adding the current character to the prefix traverse the trie pointer to the node representing prefix.
  4. Now traverse the tree from curr pointer in a preorder fashion and record whenever we encounter a complete word.
  5. Limit the result to 3 and return dfs once reached this limit.
  6. Add the words to the final result.

Adding a word “mouse”, “money” to TRIE,

Adding word “mouse”, “money” to TRIE,
/**
* @param {string[]} products
* @param {string} searchWord
* @return {string[][]}
*/
var suggestedProducts = function (products, searchWord) {

products.sort();

function Trie() {
this.children = {};
}

Trie.prototype.addWord = function (word) {
let current = this;

for (let i = 0; i < word.length; i++) {
const char = word.charAt(i);

if (!current.children[char]) {
current.children[char] = new Trie();
}
current = current.children[char];
}

current.word = word;
}

let trie = new Trie();

for (const product of products) {
trie.addWord(product);
}

const output = [];
for (let i = 0; i < searchWord.length; i++) {
const char = searchWord.charAt(i);
trie = !!trie ? trie.children[char] : null;
output.push(!!trie ? dfs(trie) : []);
}

return output;

function dfs(node, output = []) {
if (!!node.word) {
output.push(node.word);
}

for (const child in node.children) {
dfs(node.children[child], output)
}

return output.length >= 3 ? output.slice(0, 3) : output;
}

};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store