成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Implement Trie 實現(xiàn)前綴樹

jsliang / 1198人閱讀

摘要：壓縮前綴樹其實就是將所有只有一個子節(jié)點的節(jié)點合并成一個，以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。

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.
哈希表法 復(fù)雜度

時間 插入和查詢都是O(K) K是詞的長度 空間 O(NK) N是字典里詞的個數(shù)

思路

前綴樹的具體講解請戳這篇博客。這里我們實現(xiàn)樹節(jié)點時使用了哈希表來映射字母和子節(jié)點的關(guān)系。
insert()：對于插入操作，我們遍歷字符串同時，根據(jù)上一個節(jié)點的哈希表來找到下一個節(jié)點，直到哈希表中沒有相應(yīng)的字母，我們就新建一個節(jié)點。然后從這個新建節(jié)點開始，用同樣的方法把剩余的字母添加完。記住最后一個字母要添加葉子節(jié)點的標(biāo)記，表明這個詞到此已經(jīng)完整了。
search()：對于搜索操作，我們也是遍歷字符串，然后根據(jù)每個節(jié)點的哈希表找到路徑，最后返回該字符串最后一個字母所在節(jié)點。如果中途有找不到路徑的情況就直接返回null，如果找到了最后的節(jié)點，如果它也是葉子結(jié)點的話，就說明找到了。
startWith()：使用和search()，一樣的方法，只是我們返回的節(jié)點不用判斷是否是葉子節(jié)點。只要找到就行。

代碼 
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;
            // 如果已有該字母的節(jié)點，則轉(zhuǎn)向該節(jié)點
            if(children.containsKey(word.charAt(i))){
                next = children.get(word.charAt(i));
            } else {
            // 如果沒有該字母的節(jié)點，就新建一個節(jié)點
                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");
后續(xù) Follow Up

Q：給定一個標(biāo)準(zhǔn)前綴樹，請寫一段程序?qū)⑵鋲嚎s。
A：壓縮前綴樹其實就是將所有只有一個子節(jié)點的節(jié)點合并成一個，以減少沒有意義的類似鏈表式的鏈接。

首先我們先將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));
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64494.html

相關(guān)文章

  • [LintCode/LeetCode] Implement Trie

    摘要：首先，我們應(yīng)該了解字典樹的性質(zhì)和結(jié)構(gòu)，就會很容易實現(xiàn)要求的三個相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個字母的性質(zhì)。所以，在字典樹的里面，添加，和三個參數(shù)。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

    付永剛 評論0 收藏0

  • 208-實現(xiàn) Trie (前綴樹)

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

    antyiwei 評論0 收藏0

  • [Leetcode] Word Search 單詞搜索

    摘要：我們可以先用待查單詞建立一個字典樹，這樣我們在從矩陣中某個點開始深度優(yōu)先搜索時，可以直接用字典樹判斷當(dāng)前組成的字符串是否是某個單詞的前綴。字典樹同樣也提供接口，所以同樣可以用于判斷是否已經(jīng)搜索到這個詞了。 Word Search I 更新的思路與解法請訪問：https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

    objc94 評論0 收藏0

  • javascript 前綴Trie

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

    xiaochao 評論0 收藏0

  • 以太坊數(shù)據(jù)結(jié)構(gòu)MPT

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

    Honwhy 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<