文章目录
字典树模板
class Trie {
class TrieNode{//字典树的结点数据结构
boolean end;//是否是单词末尾的标识
TrieNode[] child; //26个小写字母的拖尾
public TrieNode(){
end = false;
child = new TrieNode[26];
}
}
TrieNode root;//字典树的根节点。
public Trie() {
root = new TrieNode();
}
public void insert(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
//若当前结点下没有找到要的字母，则新开结点继续插入
if (p.child[u] == null) p.child[u] = new TrieNode();
p = p.child[u];
}
p.end = true;
}
public boolean search(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (p.child[u] == null) return false;//变化点（根据题意）
p = p.child[u];
}
return p.end;
}
public boolean startsWith(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (p.child[u] == null) return false;
p = p.child[u];
}
return true;
}
}
字典树练习题
208. 实现 Trie (前缀树)
难度中等1418
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 Trie {
class TrieNode {
boolean end;
TrieNode[] child;
public TrieNode(){
end = false;
child = new TrieNode[26];
}
}
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++){
int u = s.charAt(i) - 'a';
if(p.child[u] == null) p.child[u] = new TrieNode();
p = p.child[u];
}
p.end = true;
}
public boolean search(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++){
int u = s.charAt(i) - 'a';
if(p.child[u] == null) return false;
p = p.child[u];
}
return p.end;
}
public boolean startsWith(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++){
int u = s.charAt(i) - 'a';
if(p.child[u] == null) return false;
p = p.child[u];
}
return true;
}
}
1032. 字符流
难度困难160
设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。
例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。
按下述要求实现 StreamChecker 类：
-
StreamChecker(String[] words)：构造函数，用字符串数组words初始化数据结构。 -
boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配words中的某一字符串，返回true；否则，返回false。
示例：
输入：
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
输出：
[null, false, false, false, true, false, true, false, false, false, false, false, true]
解释：
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回n False
streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True ，因为 'kl' 在 words 中
提示：
1 <= words.length <= 20001 <= words[i].length <= 200-
words[i]由小写英文字母组成 -
letter是一个小写英文字母 - 最多调用查询
4 * 104次
题解：反向建字典树，反向查询字符流
class StreamChecker {
Trie trie;
List<Character> list;
public StreamChecker(String[] words) {
trie = new Trie();
list = new ArrayList<>();
for(String w : words){
trie.insert(new StringBuilder(w).reverse().toString());
}
}
public boolean query(char letter) {
list.add(letter);
return trie.search(list);
}
}
class Trie {
class TrieNode{//字典树的结点数据结构
boolean end;//是否是单词末尾的标识
TrieNode[] child; //26个小写字母的拖尾
public TrieNode(){
end = false;
child = new TrieNode[26];
}
}
TrieNode root;//字典树的根节点。
public Trie() {
root = new TrieNode();
}
public void insert(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
//若当前结点下没有找到要的字母，则新开结点继续插入
if (p.child[u] == null) p.child[u] = new TrieNode();
p = p.child[u];
}
p.end = true;
}
public boolean search(List<Character> list) {
TrieNode p = root;
for(int i = list.size() - 1; i >= 0; i--) {
int u = list.get(i) - 'a';
if(p.end == true) return true;
if (p.child[u] == null) return false;
p = p.child[u];
}
return p.end;
}
}
648. 单词替换
难度中等272
在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子。
示例 1：
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
示例 2：
输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"
提示：
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100-
dictionary[i]仅由小写字母组成。 1 <= sentence.length <= 10^6-
sentence仅由小写字母和空格组成。 -
sentence中单词的总量在范围[1, 1000]内。 -
sentence中每个单词的长度在范围[1, 1000]内。 -
sentence中单词之间由一个空格隔开。 -
sentence没有前导或尾随空格。
题解：search时查看有没有到end
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Trie trie = new Trie(dictionary);
String[] strs = sentence.split(" ");
StringBuilder sb = new StringBuilder();
for(int i = 0; i < strs.length; i++){
sb.append(trie.search(strs[i]));
if(i != strs.length-1) sb.append(" ");
}
return sb.toString();
}
}
class Trie {
class trieNode {
boolean end;
trieNode[] child;
public trieNode() {
end = false;
child = new trieNode[26];
}
}
trieNode root;
public Trie(List<String> dictionary){
root = new trieNode();
for(int i = 0; i < dictionary.size(); i++){
this.insert(dictionary.get(i));
}
}
public void insert(String s){
trieNode p = root;
for(int i = 0; i < s.length(); i++){
int u = s.charAt(i) - 'a';
if(p.child[u] == null) p.child[u] = new trieNode();
p = p.child[u];
}
p.end = true;
}
public String search(String s){
trieNode p = root;
for(int i = 0; i < s.length(); i++){
int u = s.charAt(i) - 'a';
if(p.end == true) return s.substring(0,i);
if(p.child[u] == null) return s;
p = p.child[u];
}
return s;
}
}
720. 词典中最长的单词
难度中等330
给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
示例 1：
输入：words = ["w","wo","wor","worl", "world"]
输出："world"
解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。
示例 2：
输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"
提示：
1 <= words.length <= 10001 <= words[i].length <= 30- 所有输入的字符串
words[i]都只包含小写字母。
class Solution {
public String longestWord(String[] words) {
Arrays.sort(words);
Trie trie = new Trie();
for(String s : words){
trie.insert(s);
}
String res = "";
for(int i = 0; i < words.length; i++){
if(trie.search(words[i]) && words[i].length() > res.length()){
res = words[i];
}
}
return res;
}
}
class Trie {
class TrieNode{//字典树的结点数据结构
boolean end;//是否是单词末尾的标识
TrieNode[] child; //26个小写字母的拖尾
public TrieNode(){
end = false;
child = new TrieNode[26];
}
}
TrieNode root;//字典树的根节点。
public Trie() {
root = new TrieNode();
root.end = true;
}
public void insert(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
//若当前结点下没有找到要的字母，则新开结点继续插入
if (p.child[u] == null) p.child[u] = new TrieNode();
p = p.child[u];
}
p.end = true;
}
public boolean search(String s) {
TrieNode p = root;
for(int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (p.child[u] == null || p.end == false) return false;
p = p.child[u];
}
return p.end;
}
}