【LeetCode】前缀树 trie（共14题）
2024-09-05 23:03:04
【208】Implement Trie (Prefix Tree) （2018年11月27日）
实现基本的 trie 树，包括 insert， search， startWith 操作等 api。
题解：《程序员代码面试指南》chp5， 最后一题。 里面讲了怎么实现。这个就看代码吧。没啥好说的了。
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
if (word.empty()) {return;}
const int n = word.size();
TrieNode* node = root;
int index = ;
for (int i = ; i < n; ++i) {
index = word[i] - 'a';
if (node->mp.find(index) == node->mp.end()) {
node->mp[index] = new TrieNode();
}
node = node->mp[index];
node->path++;
}
node->end++;
}
/** Returns if the word is in the trie. */
bool search(string word) {
if (word.empty()) {return false;}
TrieNode* node = root;
const int n = word.size();
int index = ;
for (int i = ; i < n; ++i) {
index = word[i] - 'a';
if (node->mp.find(index) == node->mp.end()) {
return false;
}
node = node->mp[index];
if (node->path == ) {
return false;
}
}
return node->end >= ;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
if (prefix.empty()) {return false;}
const int n = prefix.size();
TrieNode* node = root;
int index = ;
for (int i = ; i < n; ++i) {
index = prefix[i] - 'a';
if (node->mp.find(index) == node->mp.end()) {
return false;
}
node = node->mp[index];
if (node->path == ) {
return false;
}
}
return node->path >= ;
}
//define trie node
struct TrieNode{
int path; //代表多少个单词共用这个结点
int end; //代表多少个单词以这个结点结尾
map<int, TrieNode*> mp;
TrieNode() {
path = , end = ;
}
};
TrieNode* root;
};
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* bool param_2 = obj.search(word);
* bool param_3 = obj.startsWith(prefix);
*/
【211】Add and Search Word - Data structure design (2018年11月27日)
实现这两个接口：(1) void addWord(word); (2) bool search(word)。 search 的时候输入有可能是个正则表达式。'.' 字符代表任何一个字母。输入保证只有小写字母和'. 。
题解：本题比 208 题更加多了一些条件，如果 search 的时候发现 word[i]是 '.' 的时候， 用 backtracking 递归做。
class WordDictionary {
public:
struct TrieNode {
int path;
int end;
map<int, TrieNode*> mp;
TrieNode() {
path = ;
end = ;
}
};
/** Initialize your data structure here. */
WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
void addWord(string word) {
if (word.empty()) {return;}
const int n = word.size();
TrieNode* node = root;
int index = ;
for (int i = ; i < n; ++i) {
index = word[i] - 'a';
if (node->mp.find(index) == node->mp.end()) {
node->mp[index] = new TrieNode();
}
node = node->mp[index];
node->path++;
}
node->end++;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool search(string word) {
if (word.empty()) {return false;}
return search(word, , root);
}
bool search(string word, int cur, TrieNode* node) {
const int n = word.size();
if (cur == n) {
if (node->end >= ) {
return true;
}
return false;
}
if (word[cur] == '.') {
map<int, TrieNode*> mptemp = node->mp;
TrieNode* father = node;
for (auto ele : mptemp) {
node = ele.second;
if (search(word, cur+, node)) {
return true;
}
node = father;
}
return false;
} else {
int index = word[cur] - 'a';
if (node->mp.find(index) == node->mp.end()) {
return false;
}
node = node->mp[index];
if (node->path == ) {
return false;
}
return search(word, cur+, node);
}
return true;
}
TrieNode* root;
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* bool param_2 = obj.search(word);
*/
【212】Word Search II
【336】Palindrome Pairs
【421】Maximum XOR of Two Numbers in an Array
【425】Word Squares
【472】Concatenated Words
【642】Design Search Autocomplete System
【648】Replace Words
【676】Implement Magic Dictionary
【677】Map Sum Pairs （2019年3月26日）
实现两个method，
Implement a MapSum class with insert, and sum methods.
For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.
Example 1:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
题解：用trie树，用map记录当前key是否在trie树里面，如果在的话，需要覆盖当前的值。
class TrieNode {
public:
TrieNode(char _c) : c(_c), pass() {
children.resize(, nullptr);
}
char c;
vector<TrieNode*> children;
int pass = ;
};
class MapSum {
public:
/** Initialize your data structure here. */
MapSum() {
root = new TrieNode('/');
}
~MapSum() {
if (root) delete root;
}
void insert(string key, int val) {
if (cache.count(key)) {
int diff = val - cache[key];
cache[key] = val;
val = diff;
} else {
cache[key] = val;
}
TrieNode* node = root;
for (auto& c : key) {
if (node->children[c-'a'] == nullptr) {
node->children[c-'a'] = new TrieNode(c);
}
node = node->children[c-'a'];
node->pass += val;
}
}
int sum(string prefix) {
if (!root) {return ;}
TrieNode* node = root;
for (auto& c : prefix) {
if (node->children[c-'a'] == nullptr) {return ;}
node = node->children[c-'a'];
}
return node->pass;
}
TrieNode* root;
unordered_map<string, int> cache;
};
/**
* Your MapSum object will be instantiated and called as such:
* MapSum* obj = new MapSum();
* obj->insert(key,val);
* int param_2 = obj->sum(prefix);
*/
【692】Top K Frequent Words
【720】Longest Word in Dictionary （2019年2月14日，谷歌tag）
给了一个 wordlist， 返回一个最长的单词，这个单词必须是每次从尾部扔掉一个字母的单词，依然在wordlist中。
题解：我用了trie树 + sorting，先用wordlist中所有的单词insert进 trie 树，然后排序后从最长的单词开始，检查是否符合规则 ，time complexity: O(sigma(Wi) + nlogn)
class Trie {
public:
class TrieNode {
public:
TrieNode(char ch) :c(ch) {
children.resize(, nullptr);
}
~TrieNode() {
for (auto node : children) {
delete node;
}
}
char c;
vector<TrieNode*> children;
bool isEnd = false;
};
Trie(): root(new TrieNode('/')) {}
std::unique_ptr<TrieNode> root; // TrieNode* root;
void insert(string& s) {
TrieNode* cur = root.get();
for (auto& letter : s) {
if (cur->children[letter-'a'] == nullptr) {
cur->children[letter-'a'] = new TrieNode(letter);
}
cur = cur->children[letter - 'a'];
}
cur->isEnd = true;
}
bool check(string& s) {
TrieNode* cur = root.get();
for (auto& letter : s) {
cur = cur->children[letter-'a'];
if (!cur->isEnd) {return false;}
}
return true;
}
};
class Solution {
public:
string longestWord(vector<string>& words) {
Trie trie;
//sort(words.begin(), words.end(), cmp);
sort(words.begin(), words.end(),
[](const string& s1, const string& s2) {
if (s1.size() != s2.size()) {
return s1.size () > s2.size();
}
return s1 < s2;
});
for (auto& w : words) {
trie.insert(w);
}
string res = "";
for (auto& w : words) {
if (trie.check(w)) {
return w;
}
}
return "";
}
static bool cmp(const string& s1, const string& s2) {
if (s1.size() == s2.size()) {
return s1 < s2;
}
return s1.size() > s2.size();
}
};
【745】Prefix and Suffix Search
最新文章
- C# - 多线程 之 锁系统
- Android之自定义侧滑菜单
- Vector 和 ArrayList 区别
- IplImage, CvMat, Mat 的关系和相互转换(转)
- get与post需要注意的几点
- 部署tomcat在windows服务器下，将tomcat控制台日志记录到日志文件中
- GET与POST在什么情况下使用
- HDOJ/HDU 1022 Train Problem I(模拟栈)
- 在PHP网页中，如何把$_session["yyy"]赋值到一个文本框中？
- 7月12日至芯FPGA就业班招生
- HDU ACM 1098 Ignatius&#39;s puzzle
- NHibernate联合主键详细示例
- Java 程序测试_循环语句中的break和continue
- Qt中绘制五子棋棋盘
- Eureka的工作原理以及它与ZooKeeper的区别
- Linux基础上
- [转] IPTables for KVM Host
- jmeter 压力测试（一）一个简单的登录
- [转载]Oracle Golden Gate - 概念和机制 (ogg)
- spring ----> 事务:传播机制和接口TransactionDefinition
热门文章
- Spring Cloud架构教程 （六）消息驱动的微服务【Dalston版】
- 后端PHP框架laravel学习踩的各种坑
- C#配置IIS站点
- PHP必备函数详解
- VMware 虚拟化编程(13) — VMware 虚拟机的备份方案设计
- Delphi XE2 之 FireMonkey 入门(30) - 数据绑定: TBindingsList: TBindExpression 的 OnAssigningValue 事件
- 阶段1 语言基础+高级_1-3-Java语言高级_07-网络编程_第4节 模拟BS服务器案例_2_模拟BS服务器代码实现
- 阶段1 语言基础+高级_1-3-Java语言高级_04-集合_08 Map集合_11_JDK9对集合添加的优化_of方法
- node和数据库建立连接
- 应用安全-安全设备-Waf系列-软Waf-云锁