1 字典树、前缀树、Trie
将一个单词列表使用words组装起来，实现如下：（仅含有小写的字典），可以在log(m)时间内查询一个单词是否在字典中。
1.1 可能的小技巧
- 1 一些可以想到的优化：
- 1.1 如果对一个长串反复查询，则使用一个node指针指向当前查询位于Trie里面的位置，避免反复查询相同的前缀
- 1.2 如果对一个长串反复查询，尝试使用hash记录尾串的目标信息，避免对尾串反复查询
- 1.3 逆序建树，构建后缀树等等，见本篇最后两个例子
class Trie {
public:
vector<Trie *>curLevel;
bool isEnd = false;
Trie() : curLevel(26) {
}
void insert(string word) {
Trie * curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
// check nextLevel
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
}
bool search(string word) {
Trie * curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return curNode->isEnd;
}
bool startsWith(string prefix) {
Trie * curNode = this;
for(char c : prefix) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return true;
}
};
2 例题
0212 单词搜索 II
1 题目
https://leetcode-cn.com/problems/word-search-ii
2 解题思路
- 1 要搜索整个字母棋盘，很自然想到使用回溯
- 2 要知道一个字符串是否在字典里，很自然想到trie
- 3 具体解答方法
- 3.1 如下代码的注释的backTrack函数很清晰的阐述啦思路，称之为old way
- 3.2 old way的缺陷，对于tmpRes的前面的公共部分反复调用啦startWith函数重复计算啦，
- 3.3 改进，使用curNode记录tmpRes在前缀树里面的位置，那么只需要根据curNode来判断tmpRes即将加入的新的字符是否为curNode的子节点就可以啦，提升了速度
class Solution {
public:
class Trie {
public:
vector<Trie*> curLevel;
bool isEnd = false;
bool hasNext = true;
Trie() : curLevel(26) {
}
void insert(string word) {
Trie* curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
curNode->hasNext = true;
}
curNode->isEnd = true;
}
bool inTrie(string word) {
Trie* curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return curNode->isEnd;
}
bool startWith(string word) {
Trie* curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return true;
}
bool endWith(string word) {
Trie* curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return !curNode->hasNext;
}
};
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
int m = board.size();
int n = board[0].size();
// build trie in normal or reverse order
// std::shared_ptr<Trie> treeNormal = make_shared<Trie>();
Trie* treeNormal = new Trie();
// std::unique_ptr<Trie> treeReverse = new Trie();
for(auto w : words) {
treeNormal->insert(w);
// treeReverse.insert(reverse(w.begin(), w.end()));
}
int deltaX[] = {1, 0, -1, 0};
int deltaY[] = {0, 1, 0, -1};
// get the answer
vector<string> res;
unordered_set<string> hash;
for(int i = 0; i < board.size(); ++i) {
for(int j = 0; j < board[0].size(); ++j) {
// std::cout << "check next st point!" << endl;
string tmpRes = "";
vector<vector<bool>> exploredFlag(m, vector<bool>(n, false));
backTrack(i, j, board, tmpRes, res, treeNormal,
deltaX, deltaY, exploredFlag, hash
);
}
}
return res;
}
/**
[["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]]
["oath","pea","eat","rain","oathi","oathk","oathf","oate","oathii","oathfi","oathfii"]
**/
void backTrack(int i, int j, vector<vector<char>>& board, string& tmpRes, vector<string>& res, Trie* curNode,
const int* deltaX, const int* deltaY,
vector<vector<bool>>& exploredFlag,
unordered_set<string>& hash) {
char ch = board[i][j];
if(nullptr == curNode->curLevel[ch - 'a']) {
return ;
}
// start from i, j
tmpRes.push_back(board[i][j]);
// Trie* lastNode = curNode;
curNode = curNode->curLevel[ch - 'a'];
if(nullptr == curNode) {
cout << "a???" << endl;
return ;
}
// cout << "start : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
// we check the tmpRes directly using the trie
// if(tree->inTrie(tmpRes) && 0 == hash.count(tmpRes)) {
// res.emplace_back(tmpRes);
// hash.insert(tmpRes);
// if(tree->endWith(tmpRes)) {
// tmpRes.pop_back();
// return;
// }
// }
if(nullptr != curNode && curNode->isEnd == true && 0 == hash.count(tmpRes)) {
// cout << "find! >>>>> " << tmpRes << endl;
res.emplace_back(tmpRes);
hash.insert(tmpRes);
if(!curNode->hasNext) {
tmpRes.pop_back();
return;
}
}
// cout << "current[i, j] : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
exploredFlag[i][j] = true;
if(nullptr != curNode) {
// not null
for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
int nextX = i + deltaX[mvIdx];
int nextY = j + deltaY[mvIdx];
// cout << "tryStart: [x, y] :" << nextX << " " << nextY << endl;;
if( nextX < board.size() && nextX >= 0 && nextY < board[0].size() && nextY >= 0 && \
! exploredFlag[nextX][nextY]) {
backTrack(nextX, nextY, board, tmpRes, res, curNode,
deltaX, deltaY, exploredFlag, hash
);
}
// cout << "tryFinish: [x, y] :" << nextX << " " << nextY << endl;;
}
}
exploredFlag[i][j] = false;
tmpRes.pop_back();
}
// OLD WAY TO DO, will exceed the time limitation
// void backTrack(int i, int j, vector<vector<char>>& board, string& tmpRes, vector<string>& res, unique_ptr<Trie>& tree,
// const int* deltaX, const int* deltaY,
// vector<vector<bool>>& exploredFlag,
// unordered_set<string>& hash) {
// // start from i, j
// tmpRes.push_back(board[i][j]);
// // cout << "start : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
// if(tree->inTrie(tmpRes) && 0 == hash.count(tmpRes)) {
// res.emplace_back(tmpRes);
// hash.insert(tmpRes);
// if(tree->endWith(tmpRes)) {
// tmpRes.pop_back();
// return;
// }
// }
// // cout << "current[i, j] : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
// exploredFlag[i][j] = true;
// if(tree->startWith(tmpRes)) {
// for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
// int nextX = i + deltaX[mvIdx];
// int nextY = j + deltaY[mvIdx];
// if( nextX < board.size() && \
// nextX >= 0 && \
// nextY < board[0].size() && \
// nextY >= 0 && \
// ! exploredFlag[nextX][nextY]) {
// backTrack(nextX, nextY, board, tmpRes, res, tree,
// deltaX, deltaY, exploredFlag, hash
// );
// }
// // cout << "tryFinish: [x, y] :" << nextX << " " << nextY << endl;;
// }
// }
// exploredFlag[i][j] = false;
// tmpRes.pop_back();
// // cout << "current[i, j] : exit " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
// }
};
0336. 回文对
1 题目
https://leetcode-cn.com/problems/palindrome-pairs/
2 解题思路
- 1 参考官方解答：https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode-solution/
class Solution {
public:
class Trie {
public:
vector<Trie*> curLevel;
bool isEnd = false;
int wordIdx = -1;
Trie() : curLevel(26), wordIdx(-1) {
}
void insert(string& word, int idx) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
curNode->wordIdx = idx;
}
int inTrie(string word) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}
int inTrie(string& word, int left, int right) {
Trie* curNode = this;
for(int i = right; i >= left; --i) {
char c = word[i] - 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}
};
vector<vector<int>> palindromePairs(vector<string>& words) {
// travel all prefix and subfix of a word,
// find the palindrome and check the existence in the words of
// reverse of the other part
Trie* tree = new Trie();
// Trie* treeReverse = new Trie();
unordered_map<string, int> strToIdx;
// int idx = 0;
// for(auto word : words) {
// tree->insert(word);
// strToIdx[word] = idx++;
// }
// int ans = 0;
// vector<vector<int>> res = {};
// for(auto word : words) {
// deque<string> prefix;
// deque<string> subfix;
// int n = word.size();
// for(int st = 0; st <= n; ++st) {
// string pre = word.substr(0, st);
// string sub = word.substr(st);
// // cout << "p/s : " << pre << " / " << sub << endl;
// if(checkPalindrome(pre)) {
// reverse(sub.begin(), sub.end());
// if(tree->inTrie(sub)) {
// vector<int> resItem = {strToIdx[sub], strToIdx[word]};
// if(resItem[1] != resItem[0]) {
// // cout << "push: " << word + sub << endl;
// res.emplace_back(resItem);
// }
// }
// }
// if(checkPalindrome(sub) && pre.size() != n) {
// reverse(pre.begin(), pre.end());
// if(tree->inTrie(pre)) {
// vector<int> resItem = {strToIdx[word], strToIdx[pre]};
// if(resItem[1] != resItem[0]) {
// // cout << "push: " << pre + word << endl;
// res.emplace_back(vector<int>(resItem));
// }
// }
// }
// }
// }
int idx = 0;
for(auto word : words) {
// tree->insert(word, idx);
// reverse(word.begin(), word.end());
tree->insert(word, idx);
++idx;
}
int tmp = 0;
int ans = 0;
vector<vector<int>> res = {};
int curWordIdx = 0;
for(auto word : words) {
int n = word.size();
for(int st = 0; st <= n; ++st) {
string pre = word.substr(0, st);
string sub = word.substr(st);
// cout << "p/s : " << pre << " / " << sub << " curWordIdx : " << curWordIdx << endl;
// if(checkPalindrome(pre)) {
if(0 != st && checkPalindrome(word, 0, st-1)) {
// reverse(sub.begin(), sub.end());
int subIdx = tree->inTrie(word, st, n-1);
// cout << "subIdx = " << sub << "with idx = " << subIdx << endl;
if(subIdx != -1 && curWordIdx != subIdx) {
// cout << "curWordIdx / subIdx" << curWordIdx << "/" << subIdx << endl;
// cout << "push: " << sub << "+" << word << endl;
res.emplace_back(vector<int>({subIdx, curWordIdx}));
}
}
if(checkPalindrome(word, st, n-1)) {
// reverse(pre.begin(), pre.end());
int preIdx = tree->inTrie(word, 0, st-1);
if(preIdx != -1 && preIdx != curWordIdx) {
// cout << "curWordIdx / preIdx" << curWordIdx << "/" << preIdx << endl;
// cout << "push: " << pre << "+" + word << endl;
res.emplace_back(vector<int>({curWordIdx, preIdx}));
}
}
}
++curWordIdx;
}
return res;
}
// for (int i = 0; i < n; i++) {
// int m = words[i].size();
// for (int j = 0; j <= m; j++) {
// if (isPalindrome(words[i], j, m - 1)) {
// int left_id = findWord(words[i], 0, j - 1);
// if (left_id != -1 && left_id != i) {
// ret.push_back({i, left_id});
// }
// }
// if (j && isPalindrome(words[i], 0, j - 1)) {
// int right_id = findWord(words[i], j, m - 1);
// if (right_id != -1 && right_id != i) {
// ret.push_back({right_id, i});
// }
// }
// }
// }
bool checkPalindrome(string& s, int left, int right) {
int len = right - left + 1;
for(int i = 0; i < len / 2; ++i) {
if(s[left + i] != s[right - i]) {
return false;
}
}
return true;
}
// bool checkPalindrome(string& s) {
// int n = s.size();
// for(int i = 0; i < n / 2; ++i) {
// if(s[i] != s[n - i - 1]) {
// return false;
// }
// }
// return true;
// }
};
3 使用hash表来查前后缀
class Solution {
public:
class Trie {
public:
vector<Trie*> curLevel;
bool isEnd = false;
int wordIdx = -1;
Trie() : curLevel(26), wordIdx(-1) {
}
void insert(string& word, int idx) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
curNode->wordIdx = idx;
}
int inTrie(string word) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}
int inTrie(string& word, int left, int right) {
Trie* curNode = this;
for(int i = right; i >= left; --i) {
char c = word[i] - 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}
};
vector<string> wordReverse;
unordered_map<string, int> strToIdx;
int findWord(string& s, int left, int right) {
string tmp = s.substr(left, right - left + 1);
auto it = strToIdx.find(tmp);
int res = it == strToIdx.end() ? -1 : it->second;
// cout << "finding: " << tmp << " with ans = " << res << endl;
return res;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
// travel all prefix and subfix of a word,
// find the palindrome and check the existence in the words of
// reverse of the other part
int idx = 0;
for(auto word : words) {
reverse(word.begin(), word.end());
wordReverse.emplace_back(word);
strToIdx[word] = idx;
++idx;
}
vector<vector<int>> res = {};
int curWordIdx = 0;
for(auto word : words) {
int n = word.size();
for(int st = 0; st <= n; ++st) {
// cout << "p/s : " << " / " << " curWordIdx : " << curWordIdx << endl;
if(0 != st && checkPalindrome(word, 0, st-1)) {
int subIdx = findWord(word, st, n-1);
// cout << "subIdx = " << subIdx << endl;
if(subIdx != -1 && curWordIdx != subIdx) {
res.emplace_back(vector<int>({subIdx, curWordIdx}));
}
}
if(checkPalindrome(word, st, n-1)) {
int preIdx = findWord(word, 0, st-1);
if(preIdx != -1 && preIdx != curWordIdx) {
res.emplace_back(vector<int>({curWordIdx, preIdx}));
}
}
}
++curWordIdx;
}
return res;
}
bool checkPalindrome(string& s, int left, int right) {
int len = right - left + 1;
for(int i = 0; i < len / 2; ++i) {
if(s[left + i] != s[right - i]) {
return false;
}
}
return true;
}
};
0140. 单词拆分 II
1 题目
https://leetcode-cn.com/problems/word-break-ii/
2 解题思路
- 1 首先确定搜索思路：
- 1.1 很显然这个问题的解答思路不会随着问题规模的减小而改变，于是采用递归/回溯方案
- 1.2 由于需要确认当前子问题处于什么位置，于是采用回溯
- 1.3 回溯方法
- 1.3.1 每次在头部尝试字符串headWord，直到找到一个在字典里面的headWord
- 1.3.2 将原来字符串去掉headWord，然后递归到下一层
- 1.3.3 当前的headWord的所有可能尝试完毕，则回溯到尝试headWord之前，然后去尝试下一个headWord
- 1.4 以上可以看出回溯和递归的区别，递归不带有当前搜索状态，而回溯需要维持搜索状态
- 2 有了大体思路，那么如何解决: 找到一个在字典里面的headWord?
- 2.1 采用字典前缀树即可快速获得该字符串是否在字典树里面，复杂度为O(m)，m为字典树中的
class Solution {
public:
class Trie {
public:
vector<Trie*> curLevel;
bool isEnd = false;
Trie() : curLevel(26){}
void insert(string word ) {
Trie* curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
}
bool inTrie(string word) {
Trie* curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return curNode->isEnd;
}
bool startWith(string word) {
Trie* curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return true;
}
};
vector<string> wordBreak(string s, vector<string>& wordDict) {
// implement a trie to sort the word Dict
Trie* tree = new Solution::Trie();
for(string s : wordDict) {
tree->insert(s);
}
vector<string> tmpRes;
vector<vector<string>> res;
backTrack(s, tmpRes, res, tree);
vector<string> finalRes;
for(auto& strVec : res) {
string resItem = "";
for(auto& str : strVec) {
resItem += (str + " ");
}
finalRes.emplace_back(resItem.substr(0, resItem.size() - 1));
}
return finalRes;
}
void backTrack(string s, vector<string> tmpRes, vector<vector<string>>& res, Trie* trie) {
if(0 == s.size()) {
res.emplace_back(tmpRes);
}
// try every possibility
for(int i = 0; i < s.size(); ++i) {
string headWord = s.substr(0, i + 1);
tmpRes.emplace_back(headWord);
// cout << "head -> " << headWord << endl;
if(trie->inTrie(headWord)) {
// cout << "in it!" << endl;
backTrack(s.substr(i + 1), tmpRes, res, trie);
}
tmpRes.pop_back();
}
}
};
0472. 连接词
1 题目
https://leetcode-cn.com/problems/concatenated-words/
2 解题思路
- 1 首先很容易想到一点：
- 1.1 由于需要快速定位一个单词是否在字典里，则采用字典树获取该信息
- 1.2 对于一个单词，我们对于每个isEnd(也就是搜索前缀对应的单词在字典里)的位置，都从下一个字符从新开始在字典中匹配，然后每个isEnd位置后面的字符，需要继续匹配，eg：[cat, cats, catsdog, dog]，对于catsdog，从sdog和dog分别重新匹配
- 1.3 对于一个单词，它的构成成分比他小，于是将字符串排序，一边插入，一边找
- 2 通过后缀记忆剪枝dfs, eg: 对于[“a”, “aa”, “aaaa”, “aaaakaa”]中的aaaakaa，运行代码会有如下日志：
- 因为在第一次 a,a,a,a,k的时候记录了k位置往后的后缀无法成功匹配
- 那么对于后面的 aa,a,a,k以及aaa,a,k等等搜索都会直接跳过k后缀的匹配
when checking : aaaakaa the sufix start from pos : 4 has been validated to be failure!
when checking : aaaakaa the sufix start from pos : 3 has been validated to be failure!
when checking : aaaakaa the sufix start from pos : 2 has been validated to be failure!
when checking : aaaakaa the sufix start from pos : 4 has been validated to be failure!
class Solution {
public:
class Trie{
public:
vector<Trie*> curLevel;
bool isEnd = false;
// bool hasNext = false;
Trie() : curLevel(26) {
}
void insert(string& s, int idx) {
// cout << "inserting : " << s << endl;
Trie* curNode = this;
for(auto c : s) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
// curNode->hasNext = true;
}
curNode->isEnd = true;
}
};
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
int n = words.size();
Trie* tree = new Trie();
// build trie
int idx = 0;
sort(words.begin(), words.end(), [](string& a, string& b){
return a.size() < b.size();
});
vector<string> ans;
for(auto w : words) {
// cout << "-------checking " << w << endl;
// bool ableToConnect = false;
// findMaxConnectedCnt(w, 0, tree, 0, ableToConnect);
// if(ableToConnect ) {
// ans.emplace_back(w);
// }
vector<bool> trap(w.size(), false);
if(dfsToCheck(w, 0, tree, 0, trap)) {
ans.emplace_back(w);
}
tree->insert(words[idx], idx);
++idx;
}
return ans;
}
// here we search all the possible ways, but we only need one possible way, so we need return early
void findMaxConnectedCnt(string& s, int pos, Trie* root, int curCnt, bool& ableToConnect) {
if(s.size() == pos) {
if(curCnt >= 2) {
ableToConnect = true;
}
// cout << "<<<<<< finish one!" << endl;
return ;
}
int curPos = pos;
Trie* curNode = root;
while(curPos < s.size()) { // serach all prefix
int ch = s[curPos] - 'a';
if(nullptr != curNode->curLevel[ch]) {
if(curNode->curLevel[ch]->isEnd) {
// cout << ">>>>> curPos: " << curPos << " char is " << s[curPos] << " dive with curCnt: " << curCnt << endl;
// using this or next end
findMaxConnectedCnt(s, curPos + 1, root, curCnt + 1, ableToConnect);
}
} else {
return;
}
// cout << "curPos: " << curPos << " char is " << s[curPos] << " with curCnt: " << curCnt << endl;
curNode = curNode->curLevel[ch];
++curPos;
}
}
bool dfsToCheck(string& s, int pos, Trie* root, int curCnt, vector<bool>& trap) {
if(s.size() == pos) {
return curCnt >= 2;
}
if(trap[pos]) {
cout << "when checking : " << s << " the sufix start from pos : " << pos << " has been validated to be failure!" << endl;
return false;
}
int curPos = pos;
Trie* curNode = root;
while(curPos < s.size()) { // serach all prefix
int ch = s[curPos] - 'a';
if(nullptr != curNode) {
if(nullptr != curNode->curLevel[ch]) {
if(curNode->curLevel[ch]->isEnd) {
// cout << ">>>>> curPos: " << curPos << " char is " << s[curPos] << " dive with curCnt: " << curCnt << endl;
// using this or next end
if(dfsToCheck(s, curPos + 1, root, curCnt + 1, trap)) {
return true;
}
}
}
} else {
break;
}
// cout << "curPos: " << curPos << " char is " << s[curPos] << " with curCnt: " << curCnt << endl;
curNode = curNode->curLevel[ch];
++curPos;
}
trap[pos] = true;
return false;
}
};
0745WordFilter 前缀和后缀搜索
1 题目
https://leetcode-cn.com/problems/prefix-and-suffix-search/
2 解题思路
- 1 构建后缀拼接前缀树
1.1 参考解释即可：
For a word like “test”, consider “#test”, “t#test”, “st#test”, “est#test”, “test#test”. Then if we have a query like prefix = “te”, suffix = “t”, we can find it by searching for something we’ve inserted starting with “t#te”.
class WordFilter {
public:
// containning suffix
class Trie {
public:
vector<Trie*> curLevel;
int idx = -1;
Trie() : curLevel(27) {}
void insert(string& word, int idx, int left, int right) {
Trie* curNode = this;
for(int i = left; i < right; ++i) {
char c = word[i];
c = (c == '#' ? 26 : c - 'a');
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
curNode->idx = idx;
}
curNode->idx = idx;
}
int startWith(string& word) {
Trie* curNode = this;
int lastIdx = -1;
for(auto c : word) {
// cout << "checking char: " << c << endl;
c = (c == '#' ? 26 : c - 'a');
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->idx;
}
};
public:
Trie* tree;
WordFilter(vector<string>& words) {
tree = new Trie();
for(int wIdx = 0; wIdx < words.size(); ++wIdx) {
int n = words[wIdx].size();
string word = words[wIdx] + "#" + words[wIdx];
for(int j = 0; j <= n - 1; ++j) {
// string tmp = word.substr(j);
// overwrite those who start with a same suffix and prefix
// cout <<"insert : " << tmp << endl;
tree->insert(word, wIdx, j, 2*n +1);
}
}
}
int f(string prefix, string suffix) {
int ans = -1;
string tmp = suffix + "#" + prefix;
// cout << "target >> " << tmp << endl;
return tree->startWith(tmp);
}
};
1032. 字符流 StreamChecke
1 题目
https://leetcode-cn.com/problems/stream-of-characters/
2 解题思路
- 1 倒序建立搜索树即可，因为可以观察到，总是从字符流的倒序开始查询
class StreamChecker {
public:
class Trie{
public:
vector<Trie*> curLevel;
bool isEnd = false;
Trie() : curLevel(26) {}
void insert(string& word) {
Trie* curNode = this;
int n = word.size();
for(int i = n-1; i >= 0; --i) {
char c = word[i] - 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
}
bool inTrie(string& word) {
Trie* curNode = this;
int n = word.size();
for(int i = n-1; i >= 0; --i) {
char c = word[i] - 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
if(curNode->curLevel[c]->isEnd) {
return true;
}
curNode = curNode->curLevel[c];
}
return curNode->isEnd;
}
};
Trie* root;
string curStr;
StreamChecker(vector<string>& words) {
root = new Trie();
for(auto& w : words) {
root->insert(w);
}
curStr = "";
}
bool query(char letter) {
curStr += letter;
return root->inTrie(curStr);
}
};
/**
* Your StreamChecker object will be instantiated and called as such:
* StreamChecker* obj = new StreamChecker(words);
* bool param_1 = obj->query(letter);
*