lcDicTree
1 字典树、前缀树、Trie
将一个单词列表使用words组装起来，实现如下：（仅含有小写的字典），可以在log(m)时间内查询一个单词是否在字典中。
1.1 可能的小技巧
- 1 一些可以想到的优化：
- 1.1 如果对一个长串反复查询，则使用一个node指针指向当前查询位于Trie里面的位置，避免反复查询相同的前缀
- 1.2 如果对一个长串反复查询，尝试使用hash记录尾串的目标信息，避免对尾串反复查询
- 1.3 逆序建树，构建后缀树等等，见本篇最后两个例子
1 | class Trie { |
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的子节点就可以啦，提升了速度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204class 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/
1 | class Solution { |
3 使用hash表来查前后缀
1 | class Solution { |
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为字典树中的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85class 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();
}
}
};
- 2.1 采用字典前缀树即可快速获得该字符串是否在字典树里面，复杂度为O(m)，m为字典树中的
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后缀的匹配
1
2
3
4when 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!
1 | class Solution { |
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”.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64class 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 倒序建立搜索树即可，因为可以观察到，总是从字符流的倒序开始查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63class 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);
*