java - 搜索建议系统
问题描述
下面是问题陈述,下面是我使用 TrieNode 数据结构的解决方案,但我的答案是错误的,我无法理解我的代码哪里出错了,请帮助......
给定一个字符串产品数组和一个字符串 searchWord。我们想设计一个系统,在输入 searchWord 的每个字符后,从产品中最多建议三个产品名称。建议的产品应该与 searchWord 有共同的前缀。如果有超过三个具有公共前缀的产品,则返回三个按字典顺序排列的最小产品。
输入 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;
}
}
解决方案
如果我不得不猜测,除了解决方案的性能之外,功能问题可能是这样的:
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"
. 您将返回一个包含“mobile”的列表,该列表与“mou”输入不匹配。
至于性能,只需对列表进行排序,对前缀进行二进制搜索,如果它们的前缀匹配,则返回接下来的三个索引。不需要 trie(尽管将 trie 作为排序数组的索引会更好),并且不需要歌舞来对列表进行排序,只丢弃除三个值之外的所有值。
推荐阅读
- python - 当我在函数/方法中有输入时,我该如何测试它?
- java - Pentaho 不能只用一个用户登录。所有其他用户工作正常
- ms-access - 如何使用具有多个值的一个参数进行查询?
- excel - 如何计算文本框值的总和并将其打印到单元格?
- linux - 无法连接到存储库 SVN
- javascript - 如何将导入的 Slack 数据定位到 Google 表格的特定单元格中?
- android - 错误:无法访问 zzbgl 错误不断重新出现
- c - malloc 覆盖按值传递的参数
- twilio - 当用户进行特定选择时,我如何(使用 Twilio Functions 示例关键字处理程序)向外部网站发送 POST 请求?
- bash - 如何在分隔符上拆分字符串并将常量值附加到所有元素