水一篇文章。最近项目里在用字典树配合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; } };
|