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"]

Sort | Simple Traversal

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

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