搜索建议系统

Question

下面是问题陈述，下面是我使用 TrieNode 数据结构的解决方案，但我的答案是错误的，我无法理解我的代码哪里出错了，请帮助......

给定一个字符串数组 products 和一个字符串 searchWord。我们想设计一个系统，在键入 searchWord 的每个字符后，最多从产品中建议三个产品名称。建议的产品应具有与搜索词相同的前缀。如果有超过三个具有共同前缀 return 的产品，则三个字典序最小的产品。

Return 输入 searchWord 的每个字符后的建议产品列表列表。

示例 1：

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"<br>
Output: [["mobile","moneypot","monitor"],
      ["mobile","moneypot","monitor"],
     ["mouse","mousepad"],
     ["mouse","mousepad"],
     ["mouse","mousepad"]]

解释：产品按字典顺序排序 = ["mobile","moneypot","monitor","mouse","mousepad"] 输入 m 和 mo 后，所有产品都匹配，我们向用户显示 ["mobile","moneypot","monitor"] 键入 mou、mous 和 mouse 后，系统建议 ["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 1

如果我不得不猜测，除了解决方案的性能之外，功能问题可能是这样的：

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));
}

addToList函数将节点下的所有终端添加到列表中。你用 root 调用它，但你可能想用 root.child[index].

调用它

考虑输入“mou”。 root 将是表示前缀 mo 的节点，字符串将是 "u"。您将 return 一个包含“mobile”的列表，它与输入的“mou”不匹配。

至于性能，只需对列表进行排序，对前缀进行二进制搜索，如果前缀匹配，return接下来的三个索引。不需要 trie（虽然 trie 作为排序数组的索引会更好），并且不需要歌曲和舞蹈来排序列表只是为了丢弃除三个值之外的所有值。

搜索建议系统

Search Suggestions System

java

trie

data-structures