前缀树实现思路和例题

前缀树实现思路和例题前缀树实现思路和例题
前缀树实现思路和例题
前缀树:每次加字符都从头结点开始加,看有没有通向该字符的路有就复用,没有就新建。
e(end):到该字符为止,该字符串被加入几次。例如:问“bk”字符串被加入几次,发现k处的e=0,则说明一次都没被加入过。
p(pass):经过该字符有几次。例如:问以”ab“开头的字符串有几个,发现b的p=3,所以有3个。

头节点即代表有多少个以空“”开头的字符串,也代表你总共加入多少个字符串

数组(例如:26个字母)
前缀树实现思路和例题hash表
前缀树实现思路和例题
插入字符串构建前缀树
前缀树实现思路和例题
前缀树实现思路和例题
在前缀树查找字符串出现几次
前缀树实现思路和例题提前没路
前缀树实现思路和例题查找有多少个以某字符串开头的字符串
前缀树实现思路和例题
删除

前缀树实现思路和例题
你如果想删abc,是只删一次的。即沿途p–,最后一个e–
前缀树实现思路和例题
在沿途p–的时候减成0了,怎么办?
前缀树实现思路和例题删除时d的p减为0,将d下面的结点置为空,释放结点

先判断这个word之前加入过没有
前缀树实现思路和例题下一个节点p减后=0,将其下结点置空

题解

前缀树实现思路和例题
前缀树实现思路和例题
代码:

import java.util.*;


public class Solution {
    

        public class TrieTreeNode{
        public int pass;
        public int end;
        
        public TrieTreeNode[] nexts;//接下来的有26条路

        //构造方法
        public TrieTreeNode() {
            pass = 0;
            end = 0;
            nexts = new TrieTreeNode[26];
            }
        }
        
         private TrieTreeNode root=new TrieTreeNode();//根节点
     
        
         //插入方法
    public void insert(String word) {
        if (word == null) return;
        //先将字符串转为字符数组
        char[] chars = word.toCharArray();
        //从根节点开始遍历,沿途pass++
        TrieTreeNode node = root;
        node.pass++;
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            //获得要选择的那条路
            path = chars[i] - 'a';
            //如果路不存在就创建
            if (node.nexts[path] == null) {
                node.nexts[path] = new TrieTreeNode();
            }
            //路存在,就将当前节点下移,沿途pass++
            node = node.nexts[path];
            node.pass++;


        }
        //到字符串最后end++
        node.end++;
    }
    
     //删除
    public void delete(String word){
        if (word==null) return;
        //先查找一下看该字符串是否存在,存在再删除
        int searchNumbers = search(word);
        if(searchNumbers==0) return;

        char[] chars = word.toCharArray();
        //从根节点开始
        TrieTreeNode node=root;
        //根节点的pass--
        node.pass--;
        int path=0;
        for (int i = 0; i <chars.length ; i++) {
            path=chars[i]-'a';
            if(--node.nexts[path].pass==0){
                //当该节点减1后,pass变成了0(说明该节点之前插入的字符只有一次还是我们要删除的字符串,那下面就不用再查找了,直接将后面字符串置为空)
                node.nexts[path]=null;
                return;
            }

            node=node.nexts[path];//游标继续下移
        }
        node.end--;//最后将该字符串结尾的字符end--

    }
    
     //搜索方法,在前缀树查找字符串出现几次
    public int search(String word) {
        if (word == null) return 0;
        char[] chars = word.toCharArray();
        //从根节点开始遍历
        TrieTreeNode node = root;
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            path = chars[i] - 'a';
            if (node.nexts[path] == null) {
                return 0;//说明之前没有插入过
            }
            node = node.nexts[path];//之前插入过,结点下移

        }
        return node.end;//到字符串最后一个字符
    }
    
    //查找有多少个以某字符串开头的字符串(和上一个方法唯一的区别就是返回值不一样,一个是end,一个是pass)
    public int prefixNumber(String word){
        if(word==null) return 0;
        char[] chars = word.toCharArray();
        //从根节点开始
        TrieTreeNode node=root;
        int path=0;
        for (int i = 0; i <chars.length ; i++) {
            path=chars[i]-'a';
            if(node.nexts[path]==null){//没路就返回0
                return 0;
            }
            node=node.nexts[path];//有路就继续下移

        }
        return node.pass;
    }


    
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here
        ArrayList<String> list=new ArrayList();
        //TrieTree trie=new TrieTree();
        for(int i=0;i<operators.length;i++){
              if(Integer.parseInt(operators[i][0])==1){
                 insert(operators[i][1]);
              }else if(Integer.parseInt(operators[i][0])==2){
                  delete(operators[i][1]);
              }else if(Integer.parseInt(operators[i][0])==3){
                  int r=search(operators[i][1]);
                  list.add(r==0?"NO":"YES");
              }else{
                  list.add(prefixNumber(operators[i][1])+"");
              }
        }
       
        return list.toArray(new String[list.size()]);
    }
    
   

}
上一篇:算法设计与分析002


下一篇:一个简单的Android富文本TextView实现