文档章节

实现前缀树 Implement Trie (Prefix Tree)

叶枫啦啦
 叶枫啦啦
发布于 2017/11/17 13:38
字数 936
阅读 35
收藏 0

问题:

Implement a trie with insertsearch, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

解决:https://www.cnblogs.com/grandyang/p/4491665.html

【题意】实现字典树(前缀树),这道题让我们实现一个重要但又有些复杂的数据结构-字典树, 又称前缀树或单词查找树,例如,一个保存了8个键的trie结构,"A", "to", "tea", "ted", "ten", "i", "in", and "inn".如下图所示:

字典树主要有如下三点性质:

1. 根节点不包含字符,除根节点以外每个节点只包含一个字符

2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串

3. 每个节点的所有子节点包含的字符串不相同

① 一个字典树的节点应该包含字母,其子节点,以及标记其是否为叶节点的标记位。

class TrieNode{//209ms
    char c;//当前节点的字符
    Map<Character,TrieNode> children = new HashMap<>();//子节点
    boolean isLeaf;//标记是否为叶节点
    public TrieNode(){}
    public TrieNode(char c){
        this.c = c;
    }
}
public class Trie{
    private TrieNode root;
    public Trie(){
        root = new TrieNode();//初始化根节点
    }
    public void insert(String word){
        Map<Character,TrieNode> cur = root.children;//获取根节点的子节点,从它开始加入
        for (int i = 0;i < word.length() ;i ++ ) {
            char c = word.charAt(i);
            TrieNode tmp;
            if (cur.containsKey(c)) {
                tmp = cur.get(c);//获取插入的节点
            }else{
                tmp = new TrieNode(c);
                cur.put(c,tmp);
            }
            cur = tmp.children;
            if (i == word.length() - 1) {
                tmp.isLeaf = true;
            }
        }
    }
    public boolean search(String word){
        TrieNode tmp = searchNode(word);//查找前缀,并返回叶节点
        if (tmp != null && tmp.isLeaf) {
            return true;
        }else{
            return false;
        }
    }
    public boolean startsWith(String prefix){
        if (searchNode(prefix) == null) {
            return false;
        }else{
            return true;
        }
    }
    public TrieNode searchNode(String str){//查找前缀
        Map<Character,TrieNode> cur = root.children;
        TrieNode tmp = null;
        for (int i = 0;i < str.length() ;i ++ ) {
            char c = str.charAt(i);
            if (cur.containsKey(c)) {
                tmp = cur.get(c);
                cur = tmp.children;
            }else{
                return null;
            }
        }
        return tmp;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

② 使用数组提高性能。

每个trie节点只能包含'a' - 'z'字符。 所以我们可以使用一个数组来存储这个字符。

class TrieNode{//174ms
    TrieNode[] children;//每个节点用一个大小为26的数组表示,因为小写字母范围为a-z
    boolean isLeaf;
    public TrieNode(){
        children = new TrieNode[26];//初始化节点
    }
}
public class Trie{
    private TrieNode root;
    public Trie(){
        root = new TrieNode();//初始化根节点
    }
    public void insert(String word){
        TrieNode cur = root;
        for (int i = 0;i < word.length() ;i ++ ) {
            char c = word.charAt(i);
            int index = c - 'a';
            if (cur.children[index] != null) {
                cur = cur.children[index];
            }else{
                TrieNode tmp = new TrieNode();
                cur.children[index] = tmp;
                cur = tmp;
            }
        }
        cur.isLeaf = true;
    }
    public boolean search(String word){
        TrieNode tmp = searchNode(word);//查找前缀,并返回最后一个字符所在的节点
        if (tmp != null && tmp.isLeaf) {
            return true;
        }
        return false;
    }
    public boolean startsWith(String prefix){
        if (searchNode(prefix) == null) {
            return false;
        }else{
            return true;
        }
    }
    public TrieNode searchNode(String str){
        TrieNode cur = root;
        for (int i = 0;i < str.length() ;i ++ ) {
            char c = str.charAt(i);
            int index = c - 'a';
            if (cur.children[index] != null) {
                cur = cur.children[index];
            }else{
                return null;
            }
        }
        if (cur == root) {
            return null;
        }
        return cur;
    }
}
/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

③ 将TrieNode作为内部类。

class Trie{ //160ms
    class TrieNode{
        TrieNode[] children;
        boolean isLeaf;
        public TrieNode(){
            children = new TrieNode[26];
            isLeaf = false;
        }
    }
    private TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public void insert(String word){
        TrieNode cur = root;
        char[] wchar = word.toCharArray();
        for (int i = 0;i < word.length() ;i ++ ) {
            if (cur.children[wchar[i] - 'a'] != null) {
                cur = cur.children[wchar[i] - 'a'];
            }else{
                TrieNode tmp = new TrieNode();
                cur.children[wchar[i] - 'a'] = tmp;
                cur = tmp;
            }
        }
        cur.isLeaf = true;
    }
    public boolean search(String word){
        char[] wchar = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0;i < word.length() ;i ++ ) {
            if (cur.children[wchar[i] - 'a'] == null) {
                return false;
            }else{
                cur = cur.children[wchar[i] - 'a'];
            }
        }
        return cur.isLeaf;
    }
    public boolean startsWith(String word){
        if (word.length() == 0) {
            return true;
        }
        char[] wchar = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0;i < word.length() ;i ++ ) {
            if (cur.children[wchar[i] - 'a'] == null) {
                return false;
            }else{
                cur = cur.children[wchar[i] - 'a'];
            }
        }
        return true;
    }
}
/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode 208. Implement Trie (Prefix Tree) (实现Trie树)

原题 Implement a trie with , , and methods. Example: Note: You may assume that all inputs are consist of lowercase letters . All inputs are guaranteed to be non-empty strings. R......

dby_freedom
2018/12/03
0
0
[LeetCode] Replace Words 替换单词

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, foll......

机器的心脏
2017/12/06
0
0
可持久化 trie 的简单入门

可持久化 $trie$ ....又是一个表里不一的东西..... 可持久化 $trie$ 的介绍: 和主席树类似的,其实可持久化就是体现在前缀信息的维护上(搞不懂这怎么就叫做可持久化了...) $trie$ (字典树...

Judge_Cheung
2018/08/18
0
0
LeetCode 208 Implement Trie (Prefix Tree)(实现前缀树)(*)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51619848 翻译 原文 分析 其实一开始我也不懂什么是前缀树(这...

nomasp
2016/06/09
0
0
Google 面试题 | 字典里面的最长单词

专栏 | 九章算法 网址 | http://www.jiuzhang.com 三角形分割线 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案...

2018/02/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot 是所有基于 Spring 开发的项目的起点。Spring Boot 的设计是为了让你尽可能快的跑起来 Spring 应用程序并且尽可能减少你的配置文件。

Springboot框架搭建相关 Spring Boot 是所有基于 Spring 开发的项目的起点。Spring Boot 的设计是为了让你尽可能快的跑起来 Spring 应用程序并且尽可能减少你的配置文件。 什么是 Spring Boo...

AndLong
24分钟前
3
0
好程序员云计算学习路线分享软件包管理

好程序员云计算学习路线分享软件包管理,安装/查询/卸载 一、软件的类型 A. 源码包 需要编译 nginx-1.12.1.tar.gz B. 二进制包 已编译 mysql-community-common-5.7.12-1.el7.x86_64.rpm 常见...

好程序员官方
26分钟前
1
0
阿里巴巴小程序繁星计划 9月27日有话要说

2019年9月27日,阿里巴巴小程序繁星计划峰会将于杭州云栖小镇召开。这是自今年3月阿里巴巴正式对外宣布全面开启小程序发展战略,阿里云携手支付宝、淘宝、钉钉、高德联合发布“阿里巴巴小程序...

Mr_zebra
29分钟前
4
0
centos下搭建Jenkins持续集成环境(安装jenkins)

centos下搭建Jenkins持续集成环境(安装jenkins) 1、安装JDK yum install -y java 2、安装jenkins 添加Jenkins库到yum库,Jenkins将从这里下载安装。 1 wget -O /etc/yum.repos.d/jenkins.rep...

linjin200
31分钟前
4
0
JDK1.8.0_181的无限制强度加密策略文件变动

JDK1.8.0_151后的版本无需去官网下载 local_policy.jar US_export_policy.jar这个jar包,只需要修改Java\jdk1.8.0_181\jre\lib\security这目录下的java.security文件配置即可。 随着越来越多...

葉者
33分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部