LeetCode 212. 单词搜索 II
原题链接
困难
作者:
RA
,
2021-07-30 23:22:01
,
所有人可见
,
阅读 306
class Solution {
public:
struct Node {
int id;
Node *son[26];
Node() {
id = -1;
for (int i = 0; i < 26; i++) son[i] = nullptr;
}
} * root;
void insert(string word, int idx) {
Node * p = root ;
for(char c : word) {
int i = c - 'a';
if (!p->son[i]) p->son[i] = new Node();
p = p -> son[i];
}
p->id = idx;
}
unordered_set<int> res;
vector<vector<char>> g;
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
root = new Node();
g = board;
for (int i = 0; i < words.size() ; i ++) insert(words[i], i);
for (int x = 0; x < board.size(); x++) {
for (int y = 0; y < board[x].size(); y ++) {
int idx = board[x][y] - 'a';
if (root->son[idx])
dfs(x, y, root->son[idx]);
}
}
vector<string> r;
for (auto i : res) r.push_back(words[i]);
return r;
}
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
void dfs(int x, int y, Node * p) {
if (p->id != -1) {
res.insert(p->id);
}
for (int i = 0 ; i < 4 ; i ++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < g.size() && ny < g[0].size() && g[nx][ny] != '.') {
int idx = g[nx][ny] - 'a';
char t = g[x][y];
g[x][y] = '.';
if (p->son[idx]) dfs(nx, ny, p->son[idx]);
g[x][y] = t;
}
}
}
};