Search Suggestions System

Below is the problem statement and below it , is my solution using TrieNode Data structure but My ans is wrong and i am not able to understand where my code gone wrong , please help ……

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"<br>
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”]

import java.util.*;
class Solution {
class TrieNode{
    TrieNode child[];
    boolean isTerminating;
    String word;
    char ch;
    TrieNode(){
        this.child=new TrieNode[26];
        this.isTerminating=false;
        this.word="";
    }
}
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    TrieNode root=new TrieNode();
    add(root,products);
    return search(root,searchWord);
}
public void add(TrieNode root,String product[]){
    for(int i=0;i<product.length;i++)
        addWord(root,product[i],product[i]);
}
public void addWord(TrieNode root,String word,String product){
    char ch=word.charAt(0);
    int index=ch-'a';
    if(word.length() == 1){
        TrieNode node;
        if(root.child[index] == null){
            node=new TrieNode();
            node.isTerminating=true;
            node.word=product;
            root.child[index]=node;
        }
        else{
            node=new TrieNode();
            node.isTerminating=true;
            node.word=product;
        }
        return;
    }
    if(root.child[index] == null){
        TrieNode node=new TrieNode();
        root.child[index]=node;
        addWord(root,word.substring(1),product);
    }
    else
        addWord(root.child[index],word.substring(1),product);
}

//correctly working
public List<List<String>> search(TrieNode root,String word){
    List<List<String>> list=new ArrayList<>();
    for(int i=0;i<word.length();i++){
        String str=word.substring(0,i+1);
        List<String> l=searchWord(root,str);
        list.add(l);
    }
    return list;
}
public List<String> searchWord(TrieNode root,String str){
    char ch=str.charAt(0);
    int index=ch-'a';
    if(str.length() == 1){
        if(root.child[index] == null)
            return new ArrayList<>();
        List<String> l=new ArrayList<>();
        addToList(l,root);
        print(l,str);
        return sort(l);
    }
    if(root.child[index] == null)
        return new ArrayList<>();
    return searchWord(root.child[index],str.substring(1));
}
public void print(List<String> l,String str){
    System.out.print(str+" : ");
    for(int i=0;i<l.size();i++)
        System.out.print(l.get(i)+" ");
    System.out.println();
}
public void addToList(List<String> l , TrieNode root){
    if(root == null)
        return;
    for(int i=0;i<26;i++){
        if(root.child[i] != null){
            TrieNode node=root.child[i];
            if(node.isTerminating){
                l.add(node.word);
            }
            addToList(l,node);
        }
    }
}

// lexicographically sorted array

public List<String> sort(List<String> l){
    int length=l.size();
    String words[]=new String[l.size()];
    for(int i=0;i<length;i++){
        words[i]=l.get(i);
    }
    Arrays.sort(words);
    List<String> list=new ArrayList<>();
    if(length > 3){
        list.add(words[0]);
        list.add(words[1]);
        list.add(words[2]);
        return list;
    }
    for(int i=0;i<length;i++)
        list.add(words[i]);
    return list;
     }
}

Answer

If I had to guess, other than the solution’s performance, the functional problem might be this:

public List<String> searchWord(TrieNode root,String str){
    char ch=str.charAt(0);
    int index=ch-'a';
    if(str.length() == 1){
        if(root.child[index] == null)
            return new ArrayList<>();
        List<String> l=new ArrayList<>();
  
        addToList(l,root); // <<<<<<<<<<<<<<<<< THIS LINE

        print(l,str);
        return sort(l);
    }
    if(root.child[index] == null)
        return new ArrayList<>();
    return searchWord(root.child[index],str.substring(1));
}

The addToList function adds all terminals under a node to a list. You’re calling it with root, but you probably mean to call it with root.child[index].

Consider the input “mou”. root will be the node representing prefix mo, the string will be "u". You will return a list containing “mobile”, which does not match the “mou” input.

As for performance, just sort the list, do a binary search for the prefix and return the next three indexes if their prefixes match. No trie needed (though a trie as an index into a sorted array would be even better performance), and no song-and-dance is needed to sort lists only to discard all but three values.

Advertisement

Answer