当前位置:网站首页>648. Word replacement
648. Word replacement
2022-07-07 21:40:00 【anieoo】
Original link :648. Word substitution
solution:
Hash table stores prefix , Violent algorithm for comparison ,O(n^2)
class Solution {
public:
unordered_map<string, int> dict; // Store word prefixes
string replaceWords(vector<string>& dictionary, string sentence) {
string res; // Return value
for(auto &x : dictionary) dict[x]++;
vector<string> words = split(sentence, ' ');
for(auto &word : words) {
for(int i = 0;i < word.size();i++) {
string tmp = word.substr(0, i + 1);
if(dict[tmp]) {
word = tmp;
break;
}
}
}
for(int i = 0;i < words.size();i++) {
res += words[i];
if(i != words.size() - 1) res += ' ';
}
return res;
}
// String splitting function
vector<string> split(string word, char t) {
vector<string> res; // Return value
int n = word.size();
for(int i = 0;i < n;i++) {
int j = i;
string item;
while(j < n && word[j] != t) item += word[j++];
i = j;
res.push_back(item);
}
return res;
}
};
trie Trees
const int N = 1e5 + 10;
class Solution {
public:
int son[N][26], cnt[N], idx; // Build a dictionary tree
void add(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];
}
cnt[p]++; // With p Ending words +1
}
string find(string word) {
int p = 0;
for(int i = 0;i < word.size();i++) {
int u = word[i] - 'a';
if(cnt[p]) return word.substr(0, i); // If prefix appears, replace
if(!son[p][u]) break; // If no prefix exists then ,break
p = son[p][u];
}
return word;
}
// String splitting function
vector<string> split(string word, char t) {
vector<string> res; // Return value
int n = word.size();
for(int i = 0;i < n;i++) {
int j = i;
string item;
while(j < n && word[j] != t) item += word[j++];
i = j;
res.push_back(item);
}
return res;
}
string replaceWords(vector<string>& dictionary, string sentence) {
for(auto &word : dictionary) add(word); // Build a dictionary tree
vector<string> words = split(sentence, ' ');
string res; // Define the return value
for(int i = 0;i < words.size();i++) {
string tmp = find(words[i]);
res += tmp;
if(i != words.size() - 1) res += ' ';
}
return res;
}
};
边栏推荐
- [UVALive 6663 Count the Regions] (dfs + 离散化)[通俗易懂]
- FatMouse&#39; Trade (Hangdian 1009)
- Codeforces 474 F. Ant colony
- cv2.resize函数报错:error: (-215:Assertion failed) func != 0 in function ‘cv::hal::resize‘
- 反诈困境,国有大行如何破局?
- Redis - basic use (key, string, list, set, Zset, hash, geo, bitmap, hyperloglog, transaction)
- The difference between NPM uninstall and RM direct deletion
- What are the official stock trading apps in the country? Is it safe to use
- NVR硬盤錄像機通過國標GB28181協議接入EasyCVR,設備通道信息不顯示是什麼原因?
- Numerical method for solving optimal control problem (0) -- Definition
猜你喜欢
Magic weapon - sensitive file discovery tool
The little money made by the program ape is a P!
C language helps you understand pointers from multiple perspectives (1. Character pointers 2. Array pointers and pointer arrays, array parameter passing and pointer parameter passing 3. Function point
EasyCVR配置中心录像计划页面调整分辨率时的显示优化
SQL注入报错注入函数图文详解
使用枚举实现英文转盲文
An overview of the latest research progress of "efficient deep segmentation of labels" at Shanghai Jiaotong University, which comprehensively expounds the deep segmentation methods of unsupervised, ro
NVR硬盘录像机通过国标GB28181协议接入EasyCVR,设备通道信息不显示是什么原因?
Lex & yacc of Pisa proxy SQL parsing
Solve the problem of using uni app mediaerror mediaerror errorcode -5
随机推荐
[C language] advanced pointer --- do you really understand pointer?
Qt编写物联网管理平台39-报警联动
开户还得用身份证银行卡安全吗,我是小白不懂
The little money made by the program ape is a P!
How much does it cost to develop a small program mall?
Navicat connect 2002 - can't connect to local MySQL server through socket '/var/lib/mysql/mysql Sock 'solve
Magic weapon - sensitive file discovery tool
Hoj 2245 planktonic triangle cell (Mathematics)
Dry goods sharing | devaxpress v22.1 original help document download collection
NVR hard disk video recorder is connected to easycvr through the national standard gb28181 protocol. What is the reason why the device channel information is not displayed?
Redis - basic use (key, string, list, set, Zset, hash, geo, bitmap, hyperloglog, transaction)
Devil daddy B1 hearing the last barrier, break through with all his strength
[matrix multiplication] [noi 2012] [cogs963] random number generator
object-c编程tips-timer「建议收藏」
Focusing on safety in 1995, Volvo will focus on safety in the field of intelligent driving and electrification in the future
South China x99 platform chicken blood tutorial
Intelligent transportation is full of vitality. What will happen in the future? [easy to understand]
Datatable data conversion to entity
Unity3d 4.3.4f1执行项目
Tupu digital twin coal mining system to create "hard power" of coal mining