一、前缀树基础知识

1. 前缀树概念


二、前缀树知识扩展

1. 前缀树的知识

  • 略。

前缀树题目 | 基础

题目一:实现前缀树

  题目:请设计实现一棵前缀树 Trie,它有如下操作。
   > 函数 insert,在前缀树中添加一个字符串。
   > 函数 search,查找字符串。如果前缀树中包含该字符串,则返回 true;否则返回 false。
   > 函数 startWith,查找字符串前缀。如果前缀树中包含以该前缀开头的字符串,则返回 true;否则返回 false。

题目分析

难度:
思路:

参考代码

Tips:-

前缀树题目 | 前缀树的应用


题目一:替换单词

  题目:英语中有一个概念叫词根。在词根后面加上若干字符就能拼出更长的单词。例如,"an" 是一个词根,在它后面加上 "other" 就能得到另一个单词 "another"。现在给定一个由词根组成的字典和一个英语句子,如果句子中的单词在字典中有它的词根,则用它的词根替换该单词;如果单词没有词根,则保留该单词。请输出替换后的句子。例如,如果词根字典包含字符串 ["cat","bat","rat"],英语句子为 "the cattle was rattled by the battery",则替换之后的句子是 "the cat was rat by the bat"。

题目分析

难度:
思路:

参考代码

Tips:-

题目二:神奇的字典

  题目:请实现有如下两个操作的神奇字典。
   > 函数 buildDict,输入单词数组用来创建一个字典。
   > 函数 search,输入一个单词,判断能否修改该单词中的一个字符,使修改之后的单词是字典中的一个单词。

题目分析

难度:
思路:

参考代码

Tips:-

题目三:最短的单词编码

  题目:输入一个包含 n 个单词的数组,可以把它们编码成一个字符串和 n 个下标。例如,单词数组 ["time","me","bell"] 可以编码成一个字符串 "time#bell#",然后这些单词就可以通过下标 [0, 2,5] 得到。对于每个下标,都可以从编码得到的字符串中相应的位置开始扫描,直到遇到'#'字符前所经过的子字符串为单词数组中的一个单词。例如,从 "time#bell#" 下标为2的位置开始扫描,直到遇到'#'前经过子字符串 "me" 是给定单词数组的第2个单词。给定一个单词数组,请问按照上述规则把这些单词编码之后得到的最短字符串的长度是多少?如果输入的是字符串数组 ["time","me","bell"],那么编码之后最短的字符串是最短的单词编码 "time# bell#",长度是10。

题目分析

难度:
思路:

参考代码

Tips:-

题目四:单词之和

  题目:请设计实现一个类型 MapSum,它有如下两个操作。
  > 函数 insert,输入一个字符串和一个整数,在数据集合中添加一个字符串及其对应的值。如果数据集合中已经包含该字符串,则将该字符串对应的值替换成新值。
  > 函数 sum,输入一个字符串,返回数据集合中所有以该字符串为前缀的字符串对应的值之和。

题目分析

难度:
思路:

参考代码

Tips:-

题目五:最大的异或

  题目:输入一个整数数组(每个数字都大于或等于0),请计算其中任意两个数字的异或的最大值。例如,在数组 [1,3,4,7] 中,3 和 4 的异或结果最大,异或结果为 7。

题目分析

难度:
思路:

参考代码

Tips:-

三、章节小结

  略