美文网首页
实现前缀树

实现前缀树

作者: 正经龙 | 来源:发表于2019-08-13 23:14 被阅读0次

    前缀树

    计算机科学中,trie,又称前缀树字典树,是一种有序,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

    前缀树

    特点

    前缀树的查找效率高于哈希数组,但是空间消耗要大于哈希数组

    实现

    class Trie {
    
        TrieNode root;
        /** Initialize your data structure here. */
        public Trie() {
            root = new TrieNode();
        }
    
        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode node = root;
            for(char c : word.toCharArray()){
                if(node.node[c-'a']==null){
                    node.node[c-'a'] = new TrieNode();
                }
                node = node.node[c-'a'];
            }
            node.item = word;//保存当前叶子结点对应的字符串
        }
    
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode node = root;
            for(char c:word.toCharArray()){
                if(node.node[c-'a']!=null)
                    node = node.node[c-'a'];
                else
                    return false;
            }
    
            return word.equals(node.item);
        }
    
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode node = root;
            for(char c : prefix.toCharArray()){
                if(node.node[c-'a']!=null)
                    node = node.node[c-'a'];
                else
                    return false;
            }
            return true;
        }
    }
    
    
    class TrieNode{
        TrieNode []node;
        String item;
        public TrieNode(){
            node = new TrieNode[26];
            item = "";
        }
    }
    

    总结

    前缀树是字符串笔试中经常会使用到的存储数据结构,要熟练前缀树的创建与使用。

    相关文章

      网友评论

          本文标题:实现前缀树

          本文链接:https://www.haomeiwen.com/subject/mbgijctx.html