[Leetcode] Implement Trie 实现前缀树

jsliang 发布于2019-08-14 12:28 / 1162人阅读

摘要：压缩前缀树其实就是将所有只有一个子节点的节点合并成一个，以减少没有意义的类似链表式的链接。然后我们开始遍历这个前缀树。

Implement Trie

Implement a trie with insert, search, and startsWith methods.

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

哈希表法 复杂度

时间插入和查询都是O(K) K是词的长度空间 O(NK) N是字典里词的个数

思路

前缀树的具体讲解请戳这篇博客。这里我们实现树节点时使用了哈希表来映射字母和子节点的关系。
insert()：对于插入操作，我们遍历字符串同时，根据上一个节点的哈希表来找到下一个节点，直到哈希表中没有相应的字母，我们就新建一个节点。然后从这个新建节点开始，用同样的方法把剩余的字母添加完。记住最后一个字母要添加叶子节点的标记，表明这个词到此已经完整了。
search()：对于搜索操作，我们也是遍历字符串，然后根据每个节点的哈希表找到路径，最后返回该字符串最后一个字母所在节点。如果中途有找不到路径的情况就直接返回null，如果找到了最后的节点，如果它也是叶子结点的话，就说明找到了。
startWith()：使用和search()，一样的方法，只是我们返回的节点不用判断是否是叶子节点。只要找到就行。

代码

class TrieNode {
    // Initialize your data structure here.
    HashMap children = new HashMap();
    boolean isLeaf = false;
    char c;
    public TrieNode(){}
    public TrieNode(char c) {
        this.c = c;
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        HashMap children = root.children;
        for(int i = 0; i < word.length(); i++){
            TrieNode next;
            // 如果已有该字母的节点，则转向该节点
            if(children.containsKey(word.charAt(i))){
                next = children.get(word.charAt(i));
            } else {
            // 如果没有该字母的节点，就新建一个节点
                next = new TrieNode(word.charAt(i));
                children.put(word.charAt(i), next);
            }
            children = next.children;
            if(i == word.length() - 1){
                next.isLeaf = true;
            }
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode res = searchNode(word);
        if(res != null && res.isLeaf){
            return true;
        } else {
            return false;
        }
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        return searchNode(prefix) != null;
    }
    
    private TrieNode searchNode(String word){
        HashMap children = root.children;
        TrieNode next = null;
        for(int i = 0; i < word.length(); i++){
            if(children.containsKey(word.charAt(i))){
                next = children.get(word.charAt(i));
                children = next.children;
            } else {
                return null;
            }
        }
        return next;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

后续 Follow Up

Q：给定一个标准前缀树，请写一段程序将其压缩。
A：压缩前缀树其实就是将所有只有一个子节点的节点合并成一个，以减少没有意义的类似链表式的链接。

首先我们先将TrieNode稍微改一下。让它能存字符串而不只是字母。

class TrieNode {
    // Initialize your data structure here.
    HashMap children = new HashMap();
    boolean isLeaf = false;
    String str;
    public TrieNode(){}
    public TrieNode(char c) {
        this.str = String.valueOf(c);
    }
}

然后我们开始遍历这个前缀树。

public void compressTrie(Trie t){
    compress(t.getRoot());
}

private void compress(TrieNode n){
    if(n == null) return;
    if(n.children.size()==1){
        TrieNode next =    n.children.get(n.children.keySet().iterator().next());
        n.str = n.str + next.str;
        n.children = next.children;
        compress(next);
    } else {
        for(String key: n.children.keySet()){
            compress(n.children.get(key));
        }
    }
}

GPU云服务器云服务器 trie树前缀树前缀树 python 前缀表达式c语言实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64494.html

[LintCode/LeetCode] Implement Trie

摘要：首先，我们应该了解字典树的性质和结构，就会很容易实现要求的三个相似的功能插入，查找，前缀查找。既然叫做字典树，它一定具有顺序存放个字母的性质。所以，在字典树的里面，添加，和三个参数。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

付永刚 2019-08-14 15:23 评论0 收藏0
208-实现 Trie (前缀树)

摘要：前言前缀树是一种很常用的数据结构，例如我们常用的数据库索引。而关于前缀树的介绍，由于中国有关于前缀树的教程，我就不班门弄斧了，我的答案也是参考教程的思路去解答，希望可以给大家一个参考。下面是原题目实现一个前缀树，包含和这三个操作。前言前缀树是一种很常用的数据结构，例如我们常用的数据库索引。而关于前缀树的介绍，由于LeetCode中国有关于前缀树的教程，我就不班门弄斧了，我的答案也是...

antyiwei 2019-08-19 10:50 评论0 收藏0
[Leetcode] Word Search 单词搜索

摘要：我们可以先用待查单词建立一个字典树，这样我们在从矩阵中某个点开始深度优先搜索时，可以直接用字典树判断当前组成的字符串是否是某个单词的前缀。字典树同样也提供接口，所以同样可以用于判断是否已经搜索到这个词了。 Word Search I 更新的思路与解法请访问：https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

objc94 2019-08-14 12:25 评论0 收藏0
javascript 前缀Trie

摘要：很容易看出，前缀最坏情况下的查找也快过二叉搜索树。这种压缩后的被唤作前缀压缩，或直接叫前缀树，字典树。最长公共前缀和的最长公共前缀是，遍历字典树到字母时，此时这些单词的公共前缀是。引子前缀Trie, 又叫字符Tire, trie来自单词retrieval, 一开始念作tree，后来改念try，毕竟它与树是不一样的东西。网上许多文章都搞混了trie与树。 trie是通过边来储存字符...

xiaochao 2019-08-22 14:05 评论0 收藏0
以太坊数据结构MPT

摘要：是以太坊存储数据的核心数据结构，它是由和结合的一种树形结构，理解有助于我们更好的理解以太坊的数据存储。所以就有了树压缩前缀树，后面会介绍到，也被称为，中文名称默克尔树，主要用于数据集较大时的文件校验。 MPT(Merkle Patricia Tries)是以太坊存储数据的核心数据结构，它是由Merkle Tree和Patricia Tree结合的一种树形结构，理解MPT有助于我们更...

Honwhy 2019-06-27 18:59 评论0 收藏0