208-實現 Trie (前綴樹)

antyiwei 發布于2019-08-19 10:50 / 1172人閱讀

摘要：前言前綴樹是一種很常用的數據結構，例如我們常用的數據庫索引。而關于前綴樹的介紹，由于中國有關于前綴樹的教程，我就不班門弄斧了，我的答案也是參考教程的思路去解答，希望可以給大家一個參考。下面是原題目實現一個前綴樹，包含和這三個操作。

前言

前綴樹是一種很常用的數據結構，例如我們常用的數據庫索引。而關于前綴樹的介紹，由于LeetCode中國有關于前綴樹的教程，我就不班門弄斧了，我的答案也是參考教程的思路去解答，希望可以給大家一個參考。下面是原題目：

實現一個 Trie (前綴樹)，包含 insert, search, 和 startsWith 這三個操作。示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true
說明:
你可以假設所有的輸入都是由小寫字母 a-z 構成的。
保證所有輸入均為非空字符串。

解題思路

樹是由節點組成，節點定義應該包含節點值(前綴樹的定義，值應該為一個字符char)和葉子節點的指針，但是為了識別是否為一個單詞的最后一個字符，所以增加一個boolean變量識別。

由于已知輸入為全小寫(a-z)的字母，所以可以使用一個長度為26的數組存儲葉子節點。且由于a-z的ASCII碼是連續的，其ASCII是從97-123，所以可以直接使用 ASCII碼-97=對應節點的數組下標。

基于數組實現的前綴樹

class Trie {
    /**
     * 當前節點的值
     */
    public char value;
    /**
     * a-z有26個字母，需要訪問時由于a的ASCII碼為97，所以所有字母訪問的對應下表皆為 字母的ASCII碼-97
     */
    public Trie[] children=new Trie[26];
    /**
     * 標識此節點是否為某個單詞的結束節點
     */
    public boolean endAsWord=false;
    
    public Trie() {
        
    }
    /**
     * 插入一個單詞
     * @param word 單詞
     */
    public void insert(String word) {
        if(word!=null){
            //分解成字符數組
            char[] charArr=word.toCharArray();
            //模擬指針操作,記錄當前訪問到的樹的節點
            Trie currentNode=this;
            for(int i=0;i

GPU云服務器云服務器 trie樹前綴樹前綴樹 python 前綴表達式c語言實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76527.html

javascript 前綴Trie

摘要：很容易看出，前綴最壞情況下的查找也快過二叉搜索樹。這種壓縮后的被喚作前綴壓縮，或直接叫前綴樹，字典樹。最長公共前綴和的最長公共前綴是，遍歷字典樹到字母時，此時這些單詞的公共前綴是。引子前綴Trie, 又叫字符Tire, trie來自單詞retrieval, 一開始念作tree，后來改念try，畢竟它與樹是不一樣的東西。網上許多文章都搞混了trie與樹。 trie是通過邊來儲存字符...

xiaochao 2019-08-22 14:05 評論0 收藏0
[Leetcode] Implement Trie 實現前綴樹

摘要：壓縮前綴樹其實就是將所有只有一個子節點的節點合并成一個，以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

jsliang 2019-08-14 12:28 評論0 收藏0
以太坊數據結構MPT

摘要：是以太坊存儲數據的核心數據結構，它是由和結合的一種樹形結構，理解有助于我們更好的理解以太坊的數據存儲。所以就有了樹壓縮前綴樹，后面會介紹到，也被稱為，中文名稱默克爾樹，主要用于數據集較大時的文件校驗。 ??MPT(Merkle Patricia Tries)是以太坊存儲數據的核心數據結構，它是由Merkle Tree和Patricia Tree結合的一種樹形結構，理解MPT有助于我們更...

Honwhy 2019-06-27 18:59 評論0 收藏0
以太坊源碼分析--MPT樹

摘要：是以太坊中存儲區塊數據的核心數據結構，它和融合一個樹形結構，理解結構對之后學習以太坊區塊以及智能合約狀態存儲結構的模塊源碼很有幫助。 MPT(Merkle Patricia Tries)是以太坊中存儲區塊數據的核心數據結構，它Merkle Tree和Patricia Tree融合一個樹形結構，理解MPT結構對之后學習以太坊區塊header以及智能合約狀態存儲結構的模塊源碼很有幫助。首...

roadtogeek 2019-06-27 18:35 評論0 收藏0
Trie樹 php 實現敏感詞過濾

摘要：在樹中，每個節點表示一個狀態，每條邊表示一個字符，從根節點到葉子節點經過的邊即表示一個詞條。查找一個詞條最多耗費的時間只受詞條長度影響，因此的查找性能是很高的，跟哈希算法的性能相當。 Last-Modified: 2019年5月10日15:25:35 參考文章 c++ 使用map實現Trie樹關鍵詞過濾擴展，用于檢查一段文本中是否出現敏感詞，基于Double-Array Trie...

王笑朝 2019-07-01 12:46 評論0 收藏0