关于前缀树的一些题目
关于前缀树的一些题目
1、实现前缀树
-
描述：
? 请你实现 Trie 类：
? Trie() 初始化前缀树对象。
? void insert(String word) 向前缀树中插入字符串 word 。
? boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
? boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。 -
解法：
? 1、构造字典树：包含以下两个字段：
-
指向子节点的指针数组 son。对于本题而言，数组长度为26，即小写英文字母的数量。此时 son[0] 对应小写字母 a，son[1] 对应小写字母 b，…，son[25] 对应小写字母 z。
-
布尔字段 isEnd，表示该节点是否为字符串的结尾。
2、插入函数：
-
当插入一个字符时，如果这个字符不存在，就在当前节点的 son 数组中加入一个新的节点。
-
如果存在，就继续向下遍历下一个字符。
3、搜索字符串：
-
对当前字符串的每一个字符进行遍历，如果字典树中含有这个字符，就继续下一个字符，直到字符串结束或者前缀树当前节点 isEnd 为 true
-
如果不含这个字符，就直接 return false;
4、搜索前缀：
-
与搜索字符差不多，只要求含有这个前缀就好了，不是完全符合。
-
-
源码：
class Trie { private Trie[] son; private boolean isEnd; /** Initialize your data structure here. */ public Trie() { son = new Trie[26]; isEnd = false; } /** Inserts a word into the trie. */ public void insert(String word) { Trie node = this; for(int i=0; i
2、替换单词
-
描述：
? 在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子。
-
解法：
? 有了上题的经验，很容易想到使用前缀树为提供的词根建立前缀树，但是这里一个词根结束的标记，我们不能再使用 isEnd 来标记。如果结果是以词根开头的话，我们要取得词根本身，而不是一个结束标记。所以这里使用一个字符串来标记结束。
-
源码：
class Solution { private TrieNode root = new TrieNode(); public String replaceWords(Listdictionary, String sentence) { //将字典插入树 for(int i=0; i