leetcode212_字典树

水一篇文章。最近项目里在用字典树配合redis做搜索和字符串匹配,这部分不是我做的,但为了熟悉一下练练手,刷一道关于字典树的题目。
纠结要不要把刷leetcode的题目搬上来,想想还是放上来吧,毕竟这题只有16%的通过率。况且字典树这个东西以后还是会经常用得到的,算是给自己以后留个参考吧。

题目地址

字典树回溯法
我觉得这题主要还是字典树。当然说回溯法也可以,毕竟在搜索的时候根据情况,适时停止,进入下一个分支。不过我觉得更合适的说法是在dfs中增加了条件判断而已。
要说最经典的回溯问题,据我近两年的刷题经验来看,当属 八皇后 问题了,八皇后在leetcode中也有。

这题一入手就用dfs是显然的,从board上每个点开始,作dfs搜索。如何使用words,就是关键所在了。
如果根据每一个词去遍历,显然太慢了,而且会有好多重复的计算,比如两个字abcde,和abcdef有相同的前缀。而用字典树就恰当好处了。

下面是代码:

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
class Solution {
public:
class TireNode{
public:
TireNode(string p):prefix(p){
memset(next, 0, sizeof(next));
};
bool isEnd = false;
TireNode* next[26];
string prefix;
};

class Tire{
public:
Tire(){
root = new TireNode("");
}

void addString(string s){
TireNode *cur = root;
string prefix = "";
for (auto c : s){
prefix += c;
if (cur->next[c - 'a'] == NULL)
cur->next[c - 'a'] = new TireNode(prefix);
cur = cur->next[c - 'a'];
}
cur->isEnd = true;
}

TireNode *root;
};

void dfs(vector<vector<char>>& board, int x, int y, TireNode* cur, vector<string>& ret){
if (x < 0 || x >= board.size()) return;
if (y < 0 || y >= board[0].size()) return;
if (board[x][y] == '*') return;
char c = board[x][y];
if (cur == NULL || cur->next[c - 'a'] == NULL) return;
if (cur->next[c - 'a']->isEnd){
cur->next[c - 'a']->isEnd = false;
ret.push_back(cur->next[c - 'a']->prefix);
}
board[x][y] = '*';
dfs(board, x + 1, y, cur->next[c - 'a'], ret);
dfs(board, x - 1, y, cur->next[c - 'a'], ret);
dfs(board, x, y + 1, cur->next[c - 'a'], ret);
dfs(board, x, y - 1, cur->next[c - 'a'], ret);
board[x][y] = c;
};

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> ret;
if (board.size() == 0 || board[0].size() == 0) return ret;

Tire tire = Tire();
for (auto s : words){
tire.addString(s);
}

for (int i = 0; i < board.size(); ++i){
for (int j = 0; j < board[0].size(); ++j){
dfs(board, i, j, tire.root, ret);
}
}

return ret;
}
};