[LintCode/LeetCode] Implement Trie

付永刚发布于2019-08-14 15:23 / 3603人阅读

摘要：首先，我们应该了解字典树的性质和结构，就会很容易实现要求的三个相似的功能插入，查找，前缀查找。既然叫做字典树，它一定具有顺序存放个字母的性质。所以，在字典树的里面，添加，和三个参数。

Problem

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

Notice

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

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

首先，我们应该了解字典树的性质和结构，就会很容易实现要求的三个相似的功能：插入，查找，前缀查找。
既然叫做字典树，它一定具有顺序存放26个字母的性质。另外，为了实现和区别全词查找和前缀查找，应该有一个标记。所以，在字典树的class里面，添加ch，exist和children三个参数。

插入操作：建立结点pre，复制root。在pre的children[index]存放插入词汇word的第i个字符（用数字0到25表示a~z的26个字母，记作index），依次类推。若当前的children不存在，则建立大小为26的children结点数组。若children结点数组里的第index个TrieNode为空，则放入新的值为word.charAt(i)的TrieNode。然后pre前进到当前结点的children，pre.children[index]，继续循环操作word的下一个字符。直到放入word的最后一个字符以后，修改pre.exist值为true，说明pre之前的分支完整放入了word。

查找操作：同插入一样，复制root到结点pre，然后遍历查找word的每一个字符word.charAt(i)，若循环里某个pre.children[index]不存在，或者word的最后一个字符的exist标记为false，则返回false。否则，循环结束，返回true。

前缀查找操作：唯一和查找操作不同的地方，是不要求word的最后一个字符的exist标记为true。只要遍历完String prefix，就返回true。

Solution

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

public class Trie {
    private TrieNode root;

    public Trie() {
        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;
    }
}

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

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

[LintCode/LeetCode] Min Stack/Max Stack

Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...

GHOST_349178 2019-08-14 15:14 评论0 收藏0
[LintCode/LeetCode] Wildcard Matching

摘要：递归和动规的方法没有研究，说一下较为直观的贪心算法。用和两个指针分别标记和进行比较的位置，当遍历完后，若也遍历完，说明完全配对。当之前出现过，且此时和完全无法配对的时候，就一起退回在和配对过的位置。再将和逐个加继续比较，并将后移。 Problem Implement wildcard pattern matching with support for ? and *. ? Matche...

Ethan815 2019-08-14 15:43 评论0 收藏0
[LintCode/LeetCode] Intersection of Two Arrays I &

摘要：先想到的是，其实也可以，只是需要在遍历的时候，添加到数组中的数要掉，略微麻烦了一点。在里跑的时候，也要快一点。另一种类似做法的就快的多了。如果是找出所有包括重复的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

enda 2019-08-14 14:03 评论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/LeetCode] Flatten Nested List Iterator

摘要：首先，根据迭代器需要不断返回下一个元素，确定用堆栈来做。堆栈初始化数据结构，要先从后向前向堆栈压入中的元素。在调用之前，先要用判断下一个是还是，并进行的操作对要展开并顺序压入对直接返回。 Problem Given a nested list of integers, implement an iterator to flatten it. Each element is either...

spacewander 2019-08-14 15:45 评论0 收藏0