搜索建议系统TrieNode实现输出错误,求代码问题排查
搜索建议系统Trie实现问题排查
题目要求
给定字符串数组products和字符串searchWord,设计一个搜索建议系统:每输入searchWord的一个字符后,从products中推荐最多3个与当前输入拥有公共前缀的产品。如果符合条件的产品超过3个,返回字典序最小的3个产品,最终返回每一步推荐结果组成的列表。
示例输入输出
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse" Output: [ ["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"] ]
解释:products按字典序排序后为["mobile","moneypot","monitor","mouse","mousepad"],输入m和mo时所有产品都匹配,返回前3个;输入mou、mous、mouse时仅推荐["mouse","mousepad"]。
代码错误点排查
你的Trie实现存在3处核心逻辑错误:
- 单词尾节点存储逻辑错误:在
addWord方法中处理长度为1的单词时,else分支新建的节点没有挂载到父节点的child数组中,导致这部分单词直接丢失,且原有已存在的节点也没有正确标记终止状态和存储单词。 - 递归插入层级错误:在
addWord方法中,当新建子节点后递归调用的参数依然是当前的root节点,没有传入新建的子节点,导致插入操作一直停在当前层级,无法完成多字符单词的插入。 - 前缀匹配后遍历起点错误:在
searchWord方法中,匹配到长度为1的前缀后,调用addToList传入的是当前root节点,而不是匹配到的前缀对应的子节点,导致返回的结果包含了不属于当前前缀的单词。
修正后的完整代码
import java.util.*; class Solution { class TrieNode{ TrieNode child[]; boolean isTerminating; String word; 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(); root.child[index]=node; }else{ node = root.child[index]; } node.isTerminating=true; node.word=product; return; } if(root.child[index] == null){ TrieNode node=new TrieNode(); root.child[index]=node; } addWord(root.child[index],word.substring(1),product); } 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.child[index]); return sort(l); } if(root.child[index] == null) return new ArrayList<>(); return searchWord(root.child[index],str.substring(1)); } public void addToList(List<String> l , TrieNode root){ if(root == null) return; if(root.isTerminating){ l.add(root.word); } for(int i=0;i<26;i++){ if(root.child[i] != null){ addToList(l,root.child[i]); } } } 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<>(); int limit = Math.min(3, length); for(int i=0;i<limit;i++){ list.add(words[i]); } return list; } }
内容的提问来源于stack exchange,提问作者Manal jain
相关产品推荐
相关产品推荐

