当前位置：网站首页>剑指offer专项突击版第21天
剑指offer专项突击版第21天
2022-08-06 01:13:00 【hys__handsome】
自己写的版本，内存消耗击败5% 191MB。不明白什么原因，官方的思路是差不多的。
i d x idx idx 表示的是某个字符串
class Trie {
public:
int son[100010][26]{
0}, idx;
bool st[100010]{
0};
/** Initialize your data structure here. */
Trie() {
idx= 0;
}
/** Inserts a word into the trie. */
void insert(string word) {
int p = 0;
for(int i = 0; i < word.size(); i++) {
int u = word[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
st[p] = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
int p = 0;
for(int i = 0; i < word.size(); i++) {
int u = word[i]-'a';
if(!son[p][u]) return false;
p = son[p][u];
}
return st[p];
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
int p = 0;
for(int i = 0; i < prefix.size(); i++) {
int u = prefix[i]-'a';
if(!son[p][u]) return false;
p = son[p][u];
}
return true;
}
};
官解，内存消耗47.2MB
每个Trie类对象都表示一个结点。
class Trie {
private:
vector<Trie*> children;
bool isEnd;
public:
/** Initialize your data structure here. */
Trie():children(26),isEnd(false) {
}
/** Inserts a word into the trie. */
void insert(string word) {
auto node = this;
for(int i = 0; i < word.size(); i++) {
int u = word[i]-'a';
if(!node->children[u]) {
node->children[u] = new Trie();
}
node = node->children[u];
}
node->isEnd = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
auto node = searchPrefix(word);
return node && node->isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return searchPrefix(prefix);
}
Trie* searchPrefix(string word) {
auto node = this;
for(char c: word) {
c -= 'a';
if(!node->children[c]) return nullptr;
node = node->children[c];
}
return node;
}
};
字典树
- 将 d i c t i o n a r y dictionary dictionary 里的所有词根放到 t r i e trie trie 上，为了更方便操作将 s e n t e n c e sentence sentence 切割放在 v e c t o r vector vector 中，接着逐一去找 w o r d word word 的前缀是否在 t r i e trie trie 上（搜索时只需要最短路径即可），如果有就将当前 w o r d word word 替换成 t r i e trie trie 的前缀即可。最终再将所有 w o r d word word 拼接成答案。
- 注意：如果是以 s e n t e n c e sentence sentence 为字典会出现， w o r d word word 序列中相同的前缀互相替换，造成自己替换自己这就不正确了。
class Solution {
public:
int son[100010][26]{
0}, idx = 0;
bool st[100010]{
0};
string replaceWords(vector<string>& dictionary, string sentence) {
create_trie(dictionary);
vector<string> words = split(sentence,' ');
for(auto &word: words) {
word = find_root(word);
}
string res;
for(int i = 0; i < words.size() - 1; i++) {
res.append(words[i]+" ");
}
res.append(words.back());
return res;
}
void create_trie(vector<string> &dictionary) {
for(string &str: dictionary) {
int p = 0;
for(int i = 0; i < str.size(); i++) {
int u = str[i]-'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
st[p] = true;
}
}
//切割字符串
vector<string> split(string &sentence,char ch) {
int pos = 0, start;
vector<string> res;
while(pos < sentence.size()) {
while(pos < sentence.size() && sentence[pos] == ch) {
pos++;
}
start = pos;
while(pos < sentence.size() && sentence[pos] != ch) pos++;
if(start < sentence.size()){
res.emplace_back(sentence.substr(start,pos-start));
}
}
return res;
}
string find_root(string str) {
int p = 0;
string root;
for(int i = 0; i < str.size(); i++) {
int u = str[i]-'a';
//没找到说明词根不在trie上，返回原来的字符串即可
if(!son[p][u]) return str;
root += str[i];
p = son[p][u];
//找到最短路径的词根，直接返回
if(st[p]) return root;
}
return str;
}
};
由于 b u i l d D i c t buildDict buildDict 只调用一次，所以可以将他写入 t r i e trie trie 字典中，然后暴力遍历 s e a r c h W o r d searchWord searchWord 每个字符并修改，修改后查 b u i l d D i c t buildDict buildDict 的 t r i e trie trie 字典。
这个方法时间效率低下。
class MagicDictionary {
private:
struct Trie{
vector<Trie*> children;
bool isEnd;
Trie():children(26),isEnd(false){
}
}*trie;
public:
/** Initialize your data structure here. */
MagicDictionary() {
trie = new Trie();
}
void buildDict(vector<string> dictionary) {
Trie *node;
for(auto &str: dictionary) {
node = trie;
for(auto ch: str) {
ch -= 'a';
if(!node->children[ch]) {
node->children[ch] = new Trie();
}
node = node->children[ch];
}
node->isEnd = true;
}
}
bool search_word(string &word) {
auto node = trie;
for(int i = 0; i < word.size(); i++) {
int u = word[i]-'a';
if(!node->children[u]) return false;
node = node->children[u];
}
return node->isEnd;
}
bool search(string searchWord) {
for(int i = 0; i < searchWord.size(); i++) {
char ch = searchWord[i];
for(int j = 0; j < 26; j++) {
searchWord[i] = (char)(j+'a');
if(searchWord[i] != ch && search_word(searchWord)) return true;
}
searchWord[i] = ch;
}
return false;
}
};
/** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary* obj = new MagicDictionary(); * obj->buildDict(dictionary); * bool param_2 = obj->search(searchWord); */
暴力枚举，效率还更高了，可能是数据不强。
class MagicDictionary {
private:
vector<string> words;
public:
MagicDictionary() {
}
void buildDict(vector<string> dictionary) {
words = dictionary;
}
bool search(string searchWord) {
for (auto&& word: words) {
if (word.size() != searchWord.size()) {
continue;
}
int diff = 0;
for (int i = 0; i < word.size(); ++i) {
if (word[i] != searchWord[i]) {
++diff;
if (diff > 1) {
break;
}
}
}
if (diff == 1) {
return true;
}
}
return false;
}
};
官解的字典树优化，效率比我写的高很多
struct Trie {
bool is_finished;
Trie* child[26];
Trie() {
is_finished = false;
fill(begin(child), end(child), nullptr);
}
};
class MagicDictionary {
public:
MagicDictionary() {
root = new Trie();
}
void buildDict(vector<string> dictionary) {
for (auto&& word: dictionary) {
Trie* cur = root;
for (char ch: word) {
int idx = ch - 'a';
if (!cur->child[idx]) {
cur->child[idx] = new Trie();
}
cur = cur->child[idx];
}
cur->is_finished = true;
}
}
bool search(string searchWord) {
function<bool(Trie*, int, bool)> dfs = [&](Trie* node, int pos, bool modified) {
if (pos == searchWord.size()) {
return modified && node->is_finished;
}
int idx = searchWord[pos] - 'a';
if (node->child[idx]) {
if (dfs(node->child[idx], pos + 1, modified)) {
return true;
}
}
if (!modified) {
for (int i = 0; i < 26; ++i) {
if (i != idx && node->child[i]) {
if (dfs(node->child[i], pos + 1, true)) {
return true;
}
}
}
}
return false;
};
return dfs(root, 0, false);
}
private:
Trie* root;
};
边栏推荐
猜你喜欢
无监督实时系统中的基于YOLOV5_DeepSort和GaitSet外形混合步态的低像素远距离多人模式识别方法
Day6: Multiple-choice questions required for the interview
第十八天笔记
Architecture Basic Concepts and Architecture Essence
MySQL: storage engine
GPS-based NTP time synchronization server
Viola-Jones检测器（VJ）---学习笔记
STM32MP157A驱动开发 | 01- 板载LED作为系统心跳指示灯
横向联邦学习-梯度安全聚合（二）
SOAP protocol learning and use
随机推荐
golang pprof 实战
【瑞吉外卖】day01：整体介绍以及开发环境搭建
entropic force
横向联邦学习-梯度安全聚合
简单了解 JWT
多线程-实现方式
【kali-漏洞利用】（3.2）Metasploit基础（下）:MSF终端利用过程
民法常识总结1
ResultSet遍历结果集的原数据
typescript73-创建自己的类型声明文件（项目内共享类型）
Privacy Computing Overview
typescript73 - create your own type declaration files (shared types within the project)
Kubernetes Cilium展示
typescript71-已有的类型声明文件（内置声明类型文件）
Kubernetes内存泄露怎么玩
[mysql]--remember a delete delete statement using an alias pit
Vernacular Machine Learning - Convolutional Neural Network CNN
横向联邦学习-梯度安全聚合（二）
Live playback including PPT download | Build Online Deep Learning based on Flink & DeepRec
Kubernetes证书过期怎么玩