[LintCode] Implement Trie

chengjianhua 发布于2019-08-14 15:15 / 404人阅读

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树

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

转载请注明本文地址：https://www.ucloud.cn/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