2022.12.5前缀树-创新互联

TRANCE

• 1 力扣题208:前缀树
• • 1.1 题目描述
  • 1.2 思路分析
  • 1.3 代码实现

成都创新互联公司企业建站,十年网站建设经验，专注于网站建设技术，精于网页设计，有多年建站和网站代运营经验，设计师为客户打造网络企业风格，提供周到的建站售前咨询和贴心的售后服务。对于成都网站设计、网站制作中不同领域进行深入了解和探索，创新互联在网站建设中充分了解客户行业的需求，以灵动的思维在网页中充分展现，通过对客户行业精准市场调研，为客户提供的解决方案。1 力扣题208:前缀树 1.1 题目描述

Trie（发音类似 “try”）或者说 前缀树
是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

1.2 思路分析

前缀树的特点是前缀相同的字符串其树的前部分节点是相同的，构造前缀树的关键在于一个节点表示一个字母，而子节点一共有26种可能性，用长度为26的数组表示即可。一种可能性为null时表示无后继节点，一种可能性为node时还需要加个节点标记，若标记为1表明是终结字符，可构成一个字符串，否则表明是中间字符，可作为前缀但不可构成字符串。关键在于26长度的数组和节点终结符标记

1.3 代码实现

private Trie[] children;
    private boolean isEnd;

    public Trie() {children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {Trie node = this;
        for (int i = 0; i< word.length(); i++) {char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {Trie node = this;
        for (int i = 0; i< prefix.length(); i++) {char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {return null;
            }
            node = node.children[index];
        }
        return node;
    }

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：2022.12.5前缀树-创新互联
网页路径：http://cdxtjz.cn/article/djgjcd.html