精华内容
下载资源
问答
  • 前缀树

    2021-03-29 22:00:18
    什么是前缀树前缀树的结构其实算是比较简单的,因为它没有像红黑树、B树、B+树那样需要达到“平衡”的规则。前缀树的每个节点存放一个数组和当前节点存放的字母,数组的长度取决于你存放在前缀树中的字符串中的...

    什么是前缀树?

    前缀树的结构其实算是比较简单的,因为它没有像红黑树、B树、B+树那样需要达到“平衡”的规则。前缀树的每个节点存放一个数组和当前节点存放的字母,数组的长度取决于你存放在前缀树中的字符串中的字符种数。比如我存放只包含小写字母的字符串,那么我的数组26的长度就够了,如果包含大小写的字母,那就52的长度,数组中每个位置存放下个节点的路径。

    示例

    现在我们就把"bob",“alice”,“alen”,“ale”,"boob"这几个字符串存入一个前缀树。

    首先存入"bob",每层的数组里都只有一个位置里有值。
    在这里插入图片描述
    然后存入"alice",‘a’是第一个字符,放在第一层,所以根节点的数组的第二个位置我们放入’a’(这里’a’的位置画到了第一个,字符在数组里的顺序没有影响)。
    在这里插入图片描述
    我们再存入"alen",第一个字符’a’在根节点中已经有了,我们看’a’的子节点,‘l’也在’a’的子节点中,我们继续看’l’的子节点,‘l’的子节点中没有第三个字符’e’,所以我们在’l’的子节点中增加’e’,'e’没有子节点,我们创建一个子节点,最后把’n’放进去。
    在这里插入图片描述
    我们继续放入"ale",'a’在根节点中,'l’在’a’的子节点中,'e’在’l’的子节点中,所以我们不需要做操作。
    在这里插入图片描述
    最后我们放入"boob",'b’在根节点中,‘o’在’b’的子节点中,‘o’的子节点中没有’o’,所以我们增加一个’o’,第三层位置的’o’没有子节点,我们创建一个子节点,最后把’b’放进去。
    在这里插入图片描述
    结束。

    小试身手

    最后补一个前缀树相关的算法题,大家可以试一下:
    描述
    实现一个 Trie,包含 insert, search, 和 startsWith 这三个方法。

    你可以认为所有的输入都是小写字母a-z。

    样例
    样例 1:

    输入:
    insert(“lintcode”)
    search(“lint”)
    startsWith(“lint”)
    输出:
    false
    true
    样例 2:

    输入:
    insert(“lintcode”)
    search(“code”)
    startsWith(“lint”)
    startsWith(“linterror”)
    insert(“linterror”)
    search("lintcode”)
    startsWith(“linterror”)
    输出:
    false
    true
    false
    true
    true

    代码

    
    public class Trie {
    
        class Zf{
            public char value;
            public boolean flag = false;
            public List<Zf> ls = new ArrayList<>();
            public  List<Zf> head = new ArrayList<>();
    
    
            public Zf(){
    
            }
            public Zf(char value){
                this.value = value;
            }
    
            public  Zf containsHead(char a){
                for(Zf e:head){
                    if(e.value==a){
                        return e;
                    }
                }
                return null;
            }
    
            public Zf containsLs(char a){
                for(Zf e:ls){
                    if(e.value==a){
                        return e;
                    }
                }
                return null;
            }
    
        }
    
        Zf zf = new Zf();
    
        public Trie() {
            // do intialization if necessary
        }
    
        /*
         * @param word: a word
         * @return: nothing
         */
        public void insert(String word) {
            // write your code here
            Zf index =null;
            for(int i=0;i<word.length();i++){
                if(i==0){
                    if(zf.containsHead(word.charAt(i))!=null){
                        index = zf.containsHead(word.charAt(i));
                    }else{
                        Zf t = new Zf(word.charAt(i));
                        zf.head.add(t);
                        index = t;
                    }
                 //   System.out.println("head:"+index.value);
                }else{
                 //   System.out.println("index:"+index+" "+index.value + " i="+i);
                    if(index.containsLs(word.charAt(i))!=null){
                        index = index.containsLs(word.charAt(i));
                    }else{
                        Zf t = new Zf(word.charAt(i));
                        index.ls.add(t);
                        index = t;
                    }
                }
                if(word.length()==i+1){
                    index.flag=true;
                }
            }
        }
    
        /*
         * @param word: A string
         * @return: if the word is in the trie.
         */
        public boolean search(String word) {
            // write your code here
            Zf index  = null;
            if(zf.head.size()==0){
                return false;
            }
            for(int i=0;i<word.length();i++){
                if(i==0){
                    if(zf.containsHead(word.charAt(i))!=null){
                        index = zf.containsHead(word.charAt(i));
                        if(i==word.length()-1 && !index.flag){
                            return false;
                        }
                    }else{
                        return false;
                    }
                }else{
                    if(index.containsLs(word.charAt(i))!=null){
                        index = index.containsLs(word.charAt(i));
                        if(i==word.length()-1 && !index.flag){
                            return false;
                        }
                    }else{
                        return false;
                    }
                }
            }
    
            return true;
        }
    
        /*
         * @param prefix: A string
         * @return: if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            // write your code here
            Zf index = null;
            if(zf.head.size()==0){
                return false;
            }
            for(int i=0;i<prefix.length();i++){
                if(i==0){
                    if(zf.containsHead(prefix.charAt(i))!=null){
                        index = zf.containsHead(prefix.charAt(i));
                    }else{
                        return false;
                    }
                }else{
                    if(index.containsLs(prefix.charAt(i))!=null){
                        index = index.containsLs(prefix.charAt(i));
                    }else{
                        return false;
                    }
                }
            }
            return true;
        }
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,929
精华内容 5,171
关键字:

前缀树