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

    2021-03-19 16:34:24
    public class Solution { public static class TrieNode { public int pass; public int end; public TrieNode[] nexts;//字符种类不叫多的时候可以换成哈希表 HashMap<Character, Node>... public Tri

    前缀树的特性:

    1. 根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
    2. 从根节点到某一节点的路径上的字符连接起来,就是该节点对应的字符串。
    3. 每个节点的所有子节点包含的字符都不相同。
    4. 每条边对应一个字母。每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。

    前缀树的用途:

    1. 字符串的快速检索
    2. 字符串排序
    3. 词频统计
    4. 最长公共前缀
    5. 自动匹配前缀显示后缀
    public class Solution {
        public static class TrieNode {
            public int pass;
            public int end;
            public TrieNode[] nexts;//字符种类不叫多的时候可以换成哈希表 HashMap<Character, Node> nexts = new HashMap<>();
    
            //构造方法
            public TrieNode() {
                pass = 0;
                end = 0;
                nexts = new TrieNode[26];
            }
        }
    
        public static class Trie {
            private TrieNode root;
    
            public Trie() {
                root = new TrieNode();
            }
            
    		//向树中插入单词
            public void insert(String word) {
                if (word == null) {
                    return;
                }
                char[] ch = word.toCharArray();
                TrieNode node = root;
                node.pass++;
                int index = 0;
                for (char c : ch) {
                    index = c - 'a';
                    if (node.nexts[index] == null) {
                        node.nexts[index] = new TrieNode();
                    }
                    node = node.nexts[index];
                    node.pass++;
                }
                node.end++;
            }
    
            //从树中删除一个单词
            public void delete(String word) {
                if (search(word) != 0) {//确定树中加入过word,才去删除
                    char[] ch = word.toCharArray();
                    TrieNode node = root;
                    node.pass--;
                    int index = 0;
                    for (int i = 0; i < ch.length; i++) {
                        index = ch[i] = 'a';
                        if (--node.nexts[index].pass == 0) {
                            node.nexts[index] = null;
                            return;
                        }
                        node = node.nexts[index];
                    }
                    node.end--;
                }
            }
    
            //查询word加入了几次
            public int search(String word) {
                if (word == null) {
                    return 0;
                }
                char[] ch = word.toCharArray();
                TrieNode node = root;
                int index = 0;
                for (char c : ch) {
                    index = c - 'a';
                    if (node.nexts[index] == null) {
                        return 0;
                    }
                    node = node.nexts[index];
                }
                return node.end;
            }
        }
    
        //新加入的字符串中,有几个以pre为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] ch = pre.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (char c : ch) {
                index = c - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }
    

    208. 实现 Trie (前缀树)

    题目描述:

    Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

    请你实现 Trie 类:

    • Trie() 初始化前缀树对象。
    • void insert(String word) 向前缀树中插入字符串 word 。
    • boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
    • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。

    示例:

    输入
    [“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
    [[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
    输出
    [null, null, true, false, true, null, true]

    解释
    Trie trie = new Trie();
    trie.insert(“apple”);
    trie.search(“apple”); // 返回 True
    trie.search(“app”); // 返回 False
    trie.startsWith(“app”); // 返回 True
    trie.insert(“app”);
    trie.search(“app”); // 返回 True

    提示:

    • 1 <= word.length, prefix.length <= 2000
    • word 和 prefix 仅由小写英文字母组成
    • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

    代码如下:

    class TrieNode {
            public int pass;
            public int end;
            public TrieNode[] nexts;
    
            public TrieNode() {
                pass = 0;
                end = 0;
                nexts = new TrieNode[26];
            }
        }
    
    class Trie {
    
        private TrieNode root;
        /** Initialize your data structure here. */
        public Trie() {
            root = new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] ch = word.toCharArray();
            TrieNode node = root;
            node.pass++;
            int index = 0;
            for (char c : ch) {
                index = c - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new TrieNode();
                }
                node = node.nexts[index];
                node.pass++;
            }
            node.end++;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            if (word == null) {
                return false;
            }
            char[] ch = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (char c : ch) {
                index = c - 'a';
                if (node.nexts[index] == null) {
                    return false;
                }
                node = node.nexts[index];
            }
            return node.end > 0;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            if (prefix == null) {
                return false;
            }
            char[] ch = prefix.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (char c : ch) {
                index = c - 'a';
                if (node.nexts[index] == null) {
                    return false;
                }
                node = node.nexts[index];
            }
            return node.pass > 0;
        }
    }
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */
    

    执行结果:
    在这里插入图片描述

    展开全文
  • C++ 前缀

    2020-07-23 21:27:49
    参考左神前缀树写法。 每个结点包括 通过的路径数量(每个字符出现的数量) 停止点(至此前的字符串出现的数量) 接下来的字符 主要函数包括 插入字符串 word_insert 返回相同的字符串数量 word_search...struct Tri

    参考左神前缀树写法。

    每个结点包括

    • 通过的路径数量(每个字符出现的数量)
    • 停止点(至此前的字符串出现的数量)
    • 接下来的字符

    主要函数包括

    • 插入字符串 word_insert
    • 返回相同的字符串数量 word_search
    • 删除字符串 word_delete
    • 前缀数量计算 prefixNumber
    #include<iostream>
    #include<vector>
    #include<string>
    
    using namespace std;
    
    struct TrieNode {
    	int path;
    	int end;
    	TrieNode* nexts[26];
    };
    
    class Trie 
    {
    //private: 
    //	TrieNode *root;
    
    public:
    	TrieNode* root;
    	Trie() {
    		root = new TrieNode();
    	}
    	// 插入一个新的字符串,更新前缀树
    	void word_insert(string word)
    	{
    		if (word.empty())
    			return;
    		TrieNode* node = root;
    		int index = 0;
    		for (int i = 0; i < word.size(); ++i)
    		{
    			index = word[i] - 'a';
    			if (node->nexts[index] == nullptr)
    				node->nexts[index] = new TrieNode();
    			node = node->nexts[index];
    			node->path++;
    		}
    		node->end++;
    	}
    
    	// 返回与前缀相同的字符串,返回end(search(abc) 只找abc)
    	int word_search(string word)
    	{
    		if (word.empty())
    			return 0;
    		TrieNode* node = root;
    		int index = 0;
    		for (int i = 0; i < word.size(); ++i)
    		{
    			index = word[i] - 'a';
    			if (node->nexts[index] == nullptr)
    				return 0;
    			node = node->nexts[index];
    		}
    		return node->end;
    	}
    
    	// 计算有多少个前缀数量
    	int prefixNumber(string pre)
    	{
    		if (pre.empty())
    			return 0;
    		TrieNode* node = root;
    		int index = 0;
    		for (int i = 0; i < pre.size(); ++i)
    		{
    			index = pre[i] - 'a';
    			if (node->nexts[index] == nullptr)
    				return 0;
    			node = node->nexts[index];
    		}
    		return node->path;
    	}
    
    	// 删除字符串
    	void word_delete(string word)
    	{
    		if (word_search(word) == 0)
    			return;
    		TrieNode* node = root;
    		int index = 0;
    		for (int i = 0; i < word.size(); ++i)
    		{
    			index = word[i] - 'a';
    			//int the_path = node->nexts[index]->path;
    			if ((--(node->nexts[index]->path)) == 0)
    			{
    				// 后面的节点全部删除
    				TrieNode* next = node->nexts[index];
    				while (next)
    				{
    					TrieNode* toBeDeleted = node->nexts[index];
    					TrieNode* next = node->nexts[index];
    					node->nexts[index] = nullptr;
    					delete toBeDeleted;
    					if (i == word.size()- 1)
    						break;
    					index = word[++i] - 'a';
    				}
    				return;
    			}
    			node = node->nexts[index];
    		}
    		node->end--;
    	}
    };
    
    展开全文
  • TrieTree 前缀

    2020-04-01 12:29:32
    前缀树:理论知识不做赘述,直接看代码 1-Node节点、 树是由一个个节点组件而来,那前缀树的节点应该包含哪些基本信息呢: a-以当前节点作为末尾节点的次数 b-以当前节点作为中间节点的次数 ... Tri...

    前缀树:理论知识不做赘述,直接看代码

    1-Node节点、
    树是由一个个节点组建而来,那前缀树的节点应该包含哪些基本信息呢: 
        a-以当前节点作为末尾节点的次数
        b-以当前节点作为中间节点的次数
        c-当前节点的后续节点
    代码如下:

    	class TrieNode{
    		int path;
    		int end;
    		TrieNode [] nexts ;
    		
    		TrieNode(){
    			path = 0 ;
    			end = 0;
    			nexts = new TrieNode[26];
    		}
    	}

    当前构建的node节点用来统计单词信息,而字母只有26个,所以nexts可以用长度为26的数组代替。此处根据情况也可以使用HashMap<char,TrieNode>

    2-树结构
        树结构必须包含的基本信息
            a-根节点root
            b-插入方法insert
            c-搜索方法search,该方法应该返回包含被查找单词的个数
            d-前缀计数方法,该方法应该返回以搜索word作为前缀的单词的个数

    3-方法
        a-insert
            将单词转化为charArray,将Array中的每个char元素添加到数中
            因为之前使用了长度为26的数组来作为next,所以每个字节的index可以通过index = char[i] - 'a'得到。
            将对应位置构建出TrieNode
            增加沿途节点的path值和尾节点的end值

    public  void insert(String word){
    	if(word == null){
    		return;
    	}
    	
    	char [] chars = word.toCharArray();
    	TrieNode node = root;
    	int index = 0;
    	for(int i = 0; i < chars.length; i++){
    		index = chars[i] - 'a';
    		if(node.nexts[index] == null){
    			node.nexts[index] = new TrieNode();
    		}
    		node = node.nexts[index];
    		node.path ++;
    	}
    	node.end++;
    }	
    

        b-search
            同插入的逻辑基本相同。
            给定的word转化为charArray,一次查询每个char的next节点是否存在,如果循环过程中任意一个不存在则返回0,若循环到最后返回最后一个节点的end值。

    public int search(String word){
    	if(word == null){
    		return 0;
    	}
    	char [] chars = word.toCharArray();
    	TrieNode node = root;
    	int index = 0;
    	for(int i = 0; i < chars.length; i++){
    		index = chars[i] - 'a';
    		if(node.nexts[index] == null){
    			return 0;
    		}
    		node = node.nexts[index];
    	}
    	return node.end;
    }
    

    delete和prefixNum同理。代码如下:

    public void delete(String word){
    	if(search(word) != 0 && word == null){
    		return;
    	}
    	
    	char [] chars = word.toCharArray();
    	int index = 0;
    	TrieNode node = root;
    	for(int i = 0; i < chars.length; i++){
    		index = chars[i] - 'a';
    		if(--node.nexts[index].path == 0){
    			node.nexts[index] = null;
    			return;
    		}
    		node = node.nexts[index];
    	}
    	node.end--;
    }
    
    public int prefixNum(String word){
    	if(word == null){
    		return 0;
    	}
    	
    	TrieNode node = root;
    	char [] chars = word.toCharArray();
    	int index = 0;
    	for(int i = 0; i < chars.length; i++){
    		index = chars[i] - 'a';
    		if(node.nexts[index] == null){
    			return 0;
    		}
    		node = node.nexts[index];
    	}
    	return node.path;
    }

     

     

     

     

    展开全文
  • 使用前缀树过滤敏感词

    千次阅读 2018-08-10 14:53:37
    定义前缀树类 public class TrieNode { // 是否为关键词结尾 private boolean end = false; // 当前节点的所有的子节点 private Map&amp;lt;Character, TrieNode&amp;gt; subNodes = new HashMap&...

    定义前缀树类

    public class TrieNode {
        // 是否为关键词结尾
        private boolean end = false;
    
        // 当前节点的所有的子节点
        private Map<Character, TrieNode> subNodes = new HashMap<Character, TrieNode>();
    
        // 添加子节点
        public void addSubNode(Character key, TrieNode node) {
            this.subNodes.put(key, node);
        }
    
        // 查询子节点
        public TrieNode getSubNode(Character key) {
            return this.subNodes.get(key);
        }
    
        public boolean isEnd() {
            return end;
        }
    
        public void setEnd(boolean end) {
            this.end = end;
        }
    }

    敏感词过滤服务

    @Service
    public class SensitiveService implements InitializingBean {
        private static final Logger logger = LoggerFactory.getLogger(SensitiveService.class);
    
        // 字典树根节点
        private TrieNode rootNode = new TrieNode();
    
        /**
         * Spring在构建Bean时自动调用该方法
         * 读取敏感词文件,并构建字典树
         * @throws Exception
         */
        @Override
        public void afterPropertiesSet() throws Exception {
            try {
                // 从资源文件中读入
                InputStream in = Thread.currentThread().getContextClassLoader().
                        getResourceAsStream("sensitiveWords.txt");
                InputStreamReader isr = new InputStreamReader(in);
                BufferedReader br = new BufferedReader(isr);
    
                // 每行一个敏感词
                String line = null;
                while((line = br.readLine()) != null) {
                    addWord(br.readLine() );
                }
    
                isr.close();
            } catch (Exception e) {
                logger.error("读取敏感词文件失败" + e.getMessage());
            }
        }
    
        /**
         * 是否为非数字、大小写字母、汉字 字符
         * @param ch
         * @return
         */
        private boolean isSymbol(char ch) {
            return Pattern.matches("[^0-9a-zA-Z\u4e00-\u9fa5]", ""+ch);
        }
    
        /**
         * 增加关键词
         * @param lineText
         */
        public void addWord(String lineText) {
            TrieNode tmpNode = rootNode;
            for(int i=0; i<lineText.length(); i++) {
                Character ch = lineText.charAt(i);
                if(isSymbol(ch))
                    continue;
                TrieNode node = tmpNode.getSubNode(ch);
    
                if(node == null) {
                    node = new TrieNode();
                    tmpNode.addSubNode(ch, node);
                }
    
                tmpNode = node;
    
                if(i == lineText.length() - 1) {
                    tmpNode.setEnd(true);
                }
            }
        }
    
        /**
         * 过滤敏感词
         * @param text
         * @return
         */
        public String filter(String text) {
            if(StringUtils.isEmpty(text)) {
                return text;
            }
            // 存储过滤后的字符串
            StringBuilder result = new StringBuilder();
    
            // 敏感词替换文本
            String replaceStr = "***";
            // 字典树上的比较指针
            TrieNode tmpNode = rootNode;
            // 词首指针
            int begin = 0;
            // 位置指针
            int position = 0;
    
            while(position < text.length()) {
                // 获取带比较字符
                char ch = text.charAt(position);
    
                // 这里的比较是为了忽略敏感词间的特殊字符,比如 色-_-情
                if(isSymbol(ch)) {
                    // 如果是开头,那就直接写入结果字符串
                    if(tmpNode == rootNode) {
                        result.append(ch);
                        begin++;
                    }
                    position++;
                    continue;
                }
    
                // 读取子节点该字符对应的子节点
                tmpNode = tmpNode.getSubNode(ch);
    
                if(tmpNode == null) { // 不存在,换下个字符开头
                    result.append(text.charAt(begin));
                    position = begin + 1;
                    begin = position;
                    tmpNode = rootNode;
                } else if(tmpNode.isEnd()) { // 刚好是敏感词,替换,以敏感词后的第一个字符开头
                    // 发现敏感词
                    result.append(replaceStr);
                    position = position + 1;
                    begin = position;
                    tmpNode = rootNode;
                } else { // 有这个词,但不是敏感词,继续看看后面的词
                    position++;
                }
            }
            result.append(text.substring(begin));
    
            return result.toString();
        }
    }
    展开全文
  • 问题:在百度或大型网站,你输入“中国”出现“中国制造”,“中国创造”,好多以”中国“为前缀的字符串 前阵子JPG跟ZPG聊到了这个问题,当时懵逼ing,啥事前缀树,今日学到了便来一个总结 ... struct Tri
  • Trie 前缀树 一. 介绍 前缀树,能用图解决问题的,就不是问题 如图所示: 前缀树,可以用来表示一个字符串集合。图中字符串集合的全集S为{t,A,i,to,te,tea,ted,ten,in,inn}。代表字符的为树的边,节点表示...对于tri
  • leetcode 208 Trie前缀

    2019-09-05 18:34:52
    class Trie { public: bool indicate; //数据成员;每个节点的状态指示器,判断它及其之前的节点是否构成一个完整的字符串 Trie* pnext[26]; //数据成员;因为只限定指向了小写字母(26个英文字母) ... Tri...
  • 【JZOJ3446】三角阵(tri)

    2018-06-05 19:33:44
    problem Description 把3个相同的小三角形按如下方式连接起来就形成了一个一级三角...我们为顶端的三角阵的标记添加前缀T,为左端的三角阵的标记添加前缀L,为右端的三角阵的标记添加前缀R。 把3个二级三角阵按同...
  • 注: 前缀树:https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fromtitle=%E5%89%8D%E7%BC%80%E6%A0%91&fromid=2501595&fr=aladdin 题目: 实现一个 Trie (前缀树),包含 insert, ...tri
  • Implement a trie with insert, search, and startsWith methods. 1.前缀树的概念 所有含有公共前缀的字符串将挂在树中同一个结点下。实际上trie简明的存储了存在于串集合中的所有公共前缀。...它的标准Tri
  • 题意 给你n个字符串问你在这些字符串中是否存在一个字符串是其他字符串的前缀 思路 字典树求前缀,注意指针字典树要释放内存。 #include <iostream> #include <cstring>... Tri...
  • 题目链接 LeetCode 208. 实现 Trie (前缀树)[1] 题目描述 实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。 示例1 Trie tri...
  • * trie树 应用(trie 树也称为字典树、单词查找树,最大的特点就是共享字符串的公共前缀来达到节省空间的目的了) */ public class TrieTree { //trie树 HashMap<Character,HashMap> tri...
  • Trie(字典树、前缀树)

    2020-07-09 15:15:57
    文章目录什么是Trie?创建一棵Trie向Trie中添加元素Trie的查询操作对比二分搜索树和Trie的性能leetcode上的问题 什么是Trie?   Trie是一个多叉树,Trie专门为处理字符串而设计的。使用我们之前实现的二分...  Tri
  • Trie这个术语来自于retrieval,发音为/tri:/ “tree”,也有人读为/traɪ/ “try”。Trie树典型应用是用于快速检索(最长前缀匹配),统计,排序和保存大量的字符串,所以经常被搜索引擎系统用于文本词频统计,搜索...
  • 原题Description把3个相同的小三角形按如下...我们为顶端的三角阵的标记添加前缀T,为左端的三角阵的标记添加前缀L,为右端的三角阵的标记添加前缀R。把3个二级三角阵按同样的方式连接起来就形成了一个三级三角阵。同样
  • 问题描述: 实现一个Trie前缀树,包含insert、search和startsWith这三个操作。 问题分析: 这类的题目与堆栈的最小元素查找类似,将所有功能进行...最明显的差别就是Bool型变量来表征其节点是否为结束值,而Tri...
  • 前缀树解法: struct TrieNode { bool isEnd; TrieNode *next[26]; TrieNode() { isEnd = false; memset(next, NULL, sizeof(next)); } }; class WordDictionary { private: Tri...
  • 前言我们几乎每天都在用搜索引擎搜索信息,相信大家肯定有注意过这样一个细节:当输入某个字符的时候,搜索引框底下会出现多个推荐词,如下,输入「python」后,底下会出现挺多以python 为前缀的推荐搜索文本,它是...
  • TRIE(1)

    2018-08-14 10:36:26
     Trie又被称为前缀树或者字典树。它的基本作用是用来存储一个字符串集合:{W1, W2, W3, … WN},并且可以用来查询一个字符串S是不是在集合里  具体来说,Trie一般支持两个操作: 1. Trie.insert(W):第一个操作...
  • 贪婪算法

    2015-09-03 11:37:00
    贪婪算法分阶段的工作。在每一个阶段,就认为在这个阶段所做的... 哈弗曼编码: tri前缀码,如果一个字符放在非树叶结点上,那就不再额能够保证译码没有二义性。 转载于:https://www.cnblogs.com/chengxuyuanxia...
  • 词根、词缀笔记(二)

    2019-10-25 11:14:56
    目录前缀篇11、mis- 错12、out- 超过;外13、over- 过度14、post-... 下级19、trans- 转移20、数字前缀bi-2di-2tri-3hemi- 半semi- 半poly- 多multi- 多 前一篇词根、词缀笔记(一)https://blog.csdn.net/baidu_1947...
  • bzoj3261 最大异或和

    2019-11-11 22:59:07
    看了看可持久化trie,发现跟主席树的思想一毛一样,遵循罗哥的思想看懂算法不看代码自己实现一发就过了真爽 此题所求可以转化为在sum[l-1]----sum[r-1]中找一个数字...我们对于异或前缀和建立前i个异或前缀和的tri...
  • 很有段时间没写此系列了,今天我们来说Trie树,Trie树的名字有很多,比如字典树,前缀树等等。 一:概念 下面我们有and,as,at,cn,com这些关键词,那么如何构建tri
  • 数据结构之Trie树

    2019-09-21 04:45:12
    1、 概述 ...Trie一词来自retrieve,发音为/tri:/ “tree”,也有人读为/traɪ/ “try”。 Trie树可以利用字符串的公共前缀来节约存储空间。如下图所示,该trie树用10个节点保存了6个字符串tea,ten,...
  • 题目链接:Vitya and Strange Lesson 题意:给出一个序列,询问每次xor一个数以后的序列的mex(mex是集合中...考虑把原序列建立一棵Trie,那么显然,我们可以知道,二进制表示具有某一个特定前缀的数有多少个(即Tri
  • 题意:给一些字符串作为字典,再给一些前缀前缀为这个的有多少个单词。 思路:Trie树模板。 建立的思想不难,用指针指向下一个字符。因为字符长度不定,而且如果是26字母的话就会过长,所以用指针来做最好。那么...
  • 1.字典树的概述 ...Trie一词来自retrieve,发音为/tri:/ “tree”,也有人读为/traɪ/ “try”。 Trie树可以利用字符串的公共前缀来节约存储空间,进而可以减少查询时间,查询效率比哈希表高。2.
  • Trie树。又称字典树,单词查找树或者前缀树,是一种用于高速检索的多叉树结构。  Trie树与二叉搜索树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的全部子孙都有同样的前缀... A tri...

空空如也

空空如也

1 2 3 4 5
收藏数 85
精华内容 34
关键字:

tri前缀