[LintCode] Implement Trie

chengjianhua 發布于2019-08-14 15:15 / 409人閱讀

Problem

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

Example

insert("lintcode")
search("code") // return false
startsWith("lint") // return true
startsWith("linterror") // return false
insert("linterror")
search("lintcode) // return true
startsWith("linterror") // return true

Note

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

Solution

Insert. To insert a word(String) into a trie, by running every digit of the word in a for-loop, we have to first copy the TrieNode root into a new TrieNode cur like the way we treat TreeNode. Then we have to check if cur.children is null. If so, we create a new children with space of 26 for 26 characters from a to z. Then we check if the i-th children of cur referring to the i-th character of the word is null. If it’s null, put the character in that position, if it’s not, cur goes to the next. When the loop goes to the last digit of the word, set cur.exist to true.

Search. If we inserted several words in a trie, some branches, corresponding to some words, will have the exist tag being true. So, we still have to loop the word. Just like insert operation, if we see cur.children is null or cur.children[index] is null, the word does not exist. However, if the last-children.exist is true, the word exists.

Prefix. To check if a trie contains any words with a certain prefix, it’s the same as search. The only difference is you don’t need to check the extra digits after the prefix.

class TrieNode {
    // Initialize your data structure here.
    boolean exist;
    char ch;
    TrieNode[] children;
    public TrieNode() {   
    }
    public TrieNode(char ch) {
        this.ch = ch;
    }
}

public class Solution {
    private TrieNode root;
    public Solution() {
        root = new TrieNode();
    }
    // Inserts a word into the trie.
    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
           if (pre.children == null) {
               pre.children = new TrieNode[26];
           }
           int index = word.charAt(i) - "a";
           if (pre.children[index] == null) {
               pre.children[index] = new TrieNode(word.charAt(i));
           }
           pre = pre.children[index];
           if (i == word.length() -1) {
               pre.exist = true;
           }
        }
    }
    // Returns if the word is in the trie.
    public boolean search(String word) {
        if (word == null || word.length() == 0) {
            return false;
        }
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i)-"a";
            if (pre.children == null || pre.children[index] == null) {
                return false;
            } 
            if (i == word.length() - 1 && pre.children[index].exist == false) {
                return false;
            }
            pre = pre.children[index];
        }
        return true;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return false;
        }
        TrieNode pre = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i)-"a";
            if (pre.children == null || pre.children[index] == null) {
                return false;
            }
            pre = pre.children[index];
        }
        return true;
    }
}

GPU云服務器云服務器 Implement trie LintCode trie樹

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65509.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
[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
[LintCode] Implement Stack (using ListNode)

Problem Implement a stack. You can use any data structure inside a stack except stack itself to implement it. Example push(1)pop()push(2)top() // return 2pop()isEmpty() // return truepush(3)isEmpty()...

chenjiang3 2019-08-15 13:24 評論0 收藏0
劍指offer/LintCode40_用兩個棧模擬隊列

摘要：劍指用兩個棧模擬隊列聲明文章均為本人技術筆記，轉載請注明出處解題思路實現功能用兩個棧模擬實現一個隊列的，和操作解題思路假設有兩個棧隊列實現始終用入棧實現隊列和實現由于依次出棧并壓入中，恰好保證中順序與模擬隊列順序一致，始終保證棧頂元素為模擬劍指offer/LintCode40_用兩個棧模擬隊列聲明文章均為本人技術筆記，轉載請注明出處https://segmentfault.com...

bawn 2019-08-14 18:12 評論0 收藏0
劍指offer/LintCode494_用兩個隊列實現一個棧

摘要：劍指用兩個隊列實現一個棧聲明文章均為本人技術筆記，轉載請注明出處解題思路實現功能用兩個隊列實現一個棧，實現，，和方法解題思路假設有隊列和實現棧的操作實現棧操作始終用來入隊實現實現棧的方法模擬棧的過程中，保證兩個隊列中始終有一個隊列為空，另一劍指offer/LintCode494_用兩個隊列實現一個棧聲明文章均為本人技術筆記，轉載請注明出處https://segmentfault....

rose 2019-08-14 18:10 評論0 收藏0