You need to enable JavaScript to run this app. 搜索建议系统TrieNode实现输出错误,求代码问题排查
优惠活动
大模型
产品
解决方案
定价
更多

搜索建议系统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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.18 11:06:05