`

Implement Trie (Prefix Tree) 字典树

阅读更多
Implement a trie with insert, search, and startsWith methods.

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

设计一个字典树(前缀树),题目中假设字典中包含的字母为a-z, 我们可以设定树中每个节点都有两个属性,一个为TrieNode[], 另一个为一个布尔变量isLast。TrieNode[] 用来存放insert操作时对应的字符,isLast对应search操作是是否包含这个元素。代码如下:
class TrieNode {
    boolean isLast;
    TrieNode[] trieNode;
    // Initialize your data structure here.
    public TrieNode() {
        isLast = false;
        trieNode = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode cur = root;
        for(char c : word.toCharArray()) {
            if(cur.trieNode[c - 'a'] == null) {
                cur.trieNode[c - 'a'] = new TrieNode();
            }
            cur = cur.trieNode[c - 'a'];
        }
        cur.isLast = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode cur = root;
        for(char c : word.toCharArray()) {
            if(cur.trieNode[c - 'a'] == null) 
                return false;
            cur = cur.trieNode[c - 'a'];
        }
        return cur.isLast;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for(char c : prefix.toCharArray()) {
            if(cur.trieNode[c - 'a'] == null)
                return false;
            cur = cur.trieNode[c - 'a'];
        }
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
0
1
分享到:
评论

相关推荐

    python-leetcode题解之208-Implement-Trie-(Prefix-Tree).py

    python python_leetcode题解之208_Implement_Trie_(Prefix_Tree).py

    leetcode不会-implement-trie:树实现

    不会树实现 使用插入、搜索和startsWith 方法实现一个trie。 Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.starts...

    B+树_b+tree_

    In this project you are supposed to implement a B+ tree of order 3 with the following operations: initialize insert (with splitting) and search. The B+ tree should be able to print out itself.Input ...

    the_implement_of_java_tree.rar_The Tree_tree 数据库_tree java_数据

    树的java实现 , 很好的一个应用, ,同时结合了数据库的操作.是一个不错的学习的实例了.

    Java中extend与implement区别.doc

    Java 中 extend 与 implement 的区别 Java 语言中,extend 和 implement 是两个基本概念,它们之间的区别是非常重要的。extend 用于继承类,而 implement 用于实现接口。在 Java 中,不支持多重继承,但是可以使用...

    kdtree介绍与算法实现

    kd树很基本的算法介绍和实现方法概括。... In this assignment, you will implement a special data structure called a kd-tree (short for “k-dimensional tree”) that efficiently supports this opera- tion.

    jcifs_java_implement_cifs

    jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs jcifs_java_implement_cifs

    C Interface and Implement

    While most C programmers use APIs and the libraries that implement them in almost every application they write, relatively few programmers create and disseminate new, widely applicable APIs....

    eclipse implementor 插件

    Eclipse Implementor插件是专为Eclipse IDE设计的一款实用工具,它主要目的是为了帮助开发者更高效地实现接口或抽象类的方法。在Java编程中,当我们需要为一个接口或抽象类提供具体实现时,手动编写这些方法可能会...

    7.4.1 Packet Tracer - Implement DHCPv4

    7.4.1 Packet Tracer - Implement DHCPv4 Cisco Packet Tracer 思科模拟器 正确答案文件 由于程序问题无法保存激活DHCP端口配置 另加满分步骤截图 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次...

    6.4.1 Packet Tracer - Implement Etherchannel

    6.4.1 Packet Tracer - Implement Etherchannel Cisco Packet Tracer 思科模拟器 正确答案文件 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次转载!!! Copyright @mewhaku 2022 All Rights ...

    3.6.1 Packet Tracer - Implement VLANs and Trunking

    3.6.1 Packet Tracer - Implement VLANs and Trunking Cisco Packet Tracer 思科模拟器 正确答案文件 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次转载!!! Copyright @mewhaku 2022 All Rights ...

    C++ file implement 英文习题

    C++ 针对 文件 操作 英文习题 Read the content of a file, and output to the screen. Every time after output 10 lines, ask users if they want to stop the program.

    1.6.1 Packet Tracer - Implement a Small Network

    1.6.1 Packet Tracer - Implement a Small Network Cisco Packet Tracer 思科模拟器 正确答案文件 可直接上交正确答案文件 本答案版权归mewhaku所有,严禁再次转载!!! Copyright @mewhaku 2022 All Rights ...

    odoo 10 implement. pdf

    非完美pdf版本,但是可以看 非完美pdf版本,但是可以看

    Practical Convolutional Neural Networks Implement advanced d l models using Py

    By the end of this book, you should be ready to implement advanced, effective and efficient CNN models at your professional project or personal initiatives by working on complex image and video ...

    1、基础算法必练题(含解法)).pdf

    5. **Implement Trie (Prefix Tree)** (Medium): 实现一个前缀树(字典树)数据结构。主要用于高效地进行字符串查询和插入,适合存储单词。 6. **Add and Search Word - Data structure design** (Medium): 在一个...

    Design and Implement BI

    BI Design and implementation, BI Design and implementation, BI Design and implementation, BI Design and implementation,

    Virtualizing Tree View - 自购稀缺Unity资源

    There are also two base clases VirtualizingItemsControl and VirtualizingItemContainer which can be used to implement your own virtualizing items control. Main advantage of VirtualizingTreeView over...

    ahocorasick:使用Double Array Trie的Aho-Corasick算法的更快,更高效的Golang实现

    为了提高性能并减少内存使用,该程序使用Double Array Trie而不是常用的Linked List Trie 。 在基准测试中, it is 10 times faster than the most popular AC algorithm implement in golang @ github and tenth ...

Global site tag (gtag.js) - Google Analytics