C++实现LeetCode(208.实现字典树(前缀树))
[LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树)
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
- You may assume that all inputs are consist of lowercase letters a-z.
- All inputs are guaranteed to be non-empty strings.
这道题让我们实现一个重要但又有些复杂的数据结构-字典树， 又称前缀树或单词查找树，例如，一个保存了8个键的trie结构，"A", "to", "tea", "ted", "ten", "i", "in", and "inn"。
字典树主要有如下三点性质：
1. 根节点不包含字符，除根节点意外每个节点只包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符串不相同。
字母树的插入（Insert）、删除（ Delete）和查找（Find）都非常简单，用一个一重循环即可，即第i 次循环找到前i 个字母所对应的子树，然后进行相应的操作。实现这棵字母树，我们用最常见的数组保存（静态开辟内存）即可，当然也可以开动态的指针类型（动态开辟内存）。至于结点对儿子的指向，一般有三种方法：
1、对每个结点开一个字母集大小的数组，对应的下标是儿子所表示的字母，内容则是这个儿子对应在大数组上的位置，即标号；
2、对每个结点挂一个链表，按一定顺序记录每个儿子是谁；
3、使用左儿子右兄弟表示法记录这棵树。
三种方法，各有特点。第一种易实现，但实际的空间要求较大；第二种，较易实现，空间要求相对较小，但比较费时；第三种，空间要求最小，但相对费时且不易写。
我们这里只来实现第一种方法，这种方法实现起来简单直观，字母的字典树每个节点要定义一个大小为 26 的子节点指针数组，然后用一个标志符用来记录到当前位置为止是否为一个词，初始化的时候讲 26 个子节点都赋为空。那么 insert 操作只需要对于要插入的字符串的每一个字符算出其的位置，然后找是否存在这个子节点，若不存在则新建一个，然后再查找下一个。查找词和找前缀操作跟 insert 操作都很类似，不同点在于若不存在子节点，则返回 false。查找次最后还要看标识位，而找前缀直接返回 true 即可。代码如下：
class TrieNode {
public:
TrieNode *child[26];
bool isWord;
TrieNode(): isWord(false) {
for (auto &a : child) a = nullptr;
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
void insert(string s) {
TrieNode *p = root;
for (auto &a : s) {
int i = a - 'a';
if (!p->child[i]) p->child[i] = new TrieNode();
p = p->child[i];
}
p->isWord = true;
}
bool search(string key) {
TrieNode *p = root;
for (auto &a : key) {
int i = a - 'a';
if (!p->child[i]) return false;
p = p->child[i];
}
return p->isWord;
}
bool startsWith(string prefix) {
TrieNode *p = root;
for (auto &a : prefix) {
int i = a - 'a';
if (!p->child[i]) return false;
p = p->child[i];
}
return true;
}
private:
TrieNode* root;
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/208
类似题目：
Add and Search Word - Data structure design
Design Search Autocomplete System
参考资料：
https://leetcode.com/problems/implement-trie-prefix-tree/
到此这篇关于C++实现LeetCode(208.实现字典树(前缀树))的文章就介绍到这了,更多相关C++实现实现字典树(前缀树)内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C++实现LeetCode(199.二叉树的右侧视图)
[LeetCode] 199.Binary Tree Right Side View 二叉树的右侧视图 Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree, 1
-
C++实现LeetCode(202.快乐数)
[LeetCode] 202.Happy Number 快乐数 Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits,
-
C++实现LeetCode(207.课程清单)
[LeetCode] 207. Course Schedule 课程清单 There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given
-
C++实现LeetCode(203.移除链表元素)
[LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits
-
C++实现LeetCode(201.数字范围位相与)
[LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Credits: Special t
-
C++实现LeetCode(198.打家劫舍)
[LeetCode] 198. House Robber 打家劫舍 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security
-
C++实现LeetCode(190.颠倒二进制位)
[LeetCode] 190. Reverse Bits 颠倒二进制位 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Explanation: The input binary string 00000010100101000001111010011100 re
-
C++实现LeetCode(237.删除链表的节点)
[LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va
-
C++实现LeetCode(208.实现字典树(前缀树))
[LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树) Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app&
-
详解Java前缀树Trie的原理及代码实现
目录 Trie的概念 Trie的实现 基本结构 构建Trie 查找字符串 Trie的总结 Trie的概念 Trie(发音类似 “try”)又被称为前缀树.字典树.Trie利用字符串的公共前缀来高效地存储和检索字符串数据集中的关键词,最大限度地减少无谓的字符串比较,其核心思想是用空间换时间. Trie树可被用来实现字符串查询.前缀查询.词频统计.自动拼写.补完检查等等功能. Trie树的三个性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起
-
PHP字典树(Trie树)定义与实现方法示例
本文实例讲述了PHP字典树(Trie树)定义与实现方法.分享给大家供大家参考,具体如下: Trie树的概念(百度的解释):字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高. 我的理解是用来做字符串搜索的,每个节点只包含一个字符,比如录入单词"world",则树的结构
-
javascript trie前缀树的示例
引子 Trie树(来自单词retrieval),又称前缀字,单词查找树,字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构. 它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie的核心思想是空间换时间.利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. Trie树也有它的缺点, 假定我们只对字母与数字进行处理,那么每个节点至少有52+10个子节点.为了节省内存,我们可以用链表或数组.在JS中我们直接用数组,因为JS的数组是动态的,自带优化
-
SpringBoot使用前缀树过滤敏感词的方法实例
目录 一.前缀树 二.敏感词过滤器 总结 一.前缀树 一般设计网站的时候,会有问题发布或者是内容发布的功能,这些功能的有一个很重要的点在于如何实现敏感词过滤,要不然可能会有不良信息的发布,或者发布的内容中有夹杂可能会有恶意功能的代码片段,敏感词过滤的基本的算法是前缀树算法,前缀树也就是字典树,通过前缀树匹配可以加快敏感词匹配的速度. 前缀树又称为Trie.字典树.查找树.主要特点是:查找效率高,但内存消耗大:主要应用于字符串检索.词频统计.字符串排序等. 到底什么是前缀树?前缀树的功能是如何实现
-
详解Java中字典树(Trie树)的图解与实现
目录 简介 工作过程 数据结构 初始化 构建字典树 应用 匹配有效单词 关键词提示 总结 简介 Trie又称为前缀树或字典树,是一种有序树,它是一种专门用来处理串匹配的数据结构,用来解决一组字符中快速查找某个字符串的问题.Google搜索的关键字提示功能相信大家都不陌生,我们在输入框中进行搜索的时候,会下拉出一系列候选关键词. 上面这个关键词提示功能,底层最基本的原理就是我们今天说的数据结构:Trie树 我们先看看Tire树长什么样子,以单纯的单词匹配为例,首先它是一棵多叉树结构,根节点是一个空
-
Go 语言前缀树实现敏感词检测
目录 一.前言 二.敏感词检测 暴力匹配 正则匹配 三.Go 语言实现敏感词前缀树 前缀树结构 添加敏感词 匹配敏感词 过滤特殊字符 添加拼音检测 四.源代码 一.前言 大家都知道游戏文字.文章等一些风控场景都实现了敏感词检测,一些敏感词会被屏蔽掉或者文章无法发布.今天我就分享用Go实现敏感词前缀树来达到文本的敏感词检测,让我们一探究竟! 二.敏感词检测 实现敏感词检测都很多种方法,例如暴力.正则.前缀树等.例如一个游戏的文字交流的场景,敏感词会被和谐成 * ,该如何实现呢?首先我们先准备一些敏
-
Python容错的前缀树实现中文纠错
目录 介绍 实现 参考 介绍 本文使用 Python 实现了前缀树,并且支持编辑距离容错的查询.文中的前缀树只存储了三个分词,格式为 (分词字符串,频率) ,如:('中海晋西园', 2).('中海西园', 24).('中南海', 4),可以换成自己的文件进行数据的替换.在查询的时候要指定一个字符串和最大的容错编辑距离. 实现 class Word: def __init__(self, word, freq): self.word = word self.freq = freq class Tr
-
C++实现LeetCode(14.最长共同前缀)
[LeetCode] 14. Longest Common Prefix 最长共同前缀 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: ["flower","flow",&q
-
go语言数据结构之前缀树Trie
目录 介绍 流程 代码 初始化 插入 查找 统计以XXX开头的单词个数 删除数据 介绍 Trie树:又称为单词查找树,是一种树形结构,可以应用于统计字符串,会在搜索引擎系统中用于对文本的词频统计,下图是一个Trie树的结构,同时它也是在插入数时的一个顺序图. 流程 首先应该先创建一个结构体,里面保存的是每一个节点的信息 初始化根节点,根节点应该初始化啥?啥也不用初始化,给个空就好看上图 插入:串转字符数组:遍历数组,如果下一个节点为空,创建,则继续遍历 查找:串转字符数组,遍历如何所有字符都在树