forked from MaskRay/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
word-search-ii.cc
59 lines (54 loc) · 1.22 KB
/
word-search-ii.cc
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
// Word Search II
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
class Solution {
class TrieNode {
public:
int id;
TrieNode *c[26];
TrieNode() : id(-1) {
fill_n(c, 26, nullptr);
}
} *root;
int m, n;
vector<vector<char>> board;
vector<string> words, ans;
public:
Solution() : root(new TrieNode) {}
vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
m = board.size();
n = m ? board[0].size() : 0;
REP(i, words.size()) {
auto x = root;
for (auto c: words[i]) {
if (! x->c[c-'a'])
x->c[c-'a'] = new TrieNode;
x = x->c[c-'a'];
}
x->id = i;
}
this->board = board;
this->words = words;
ans.clear();
REP(i, m)
REP(j, n)
f(i, j, root);
return ans;
}
void f(int i, int j, TrieNode *x) {
if (board[i][j] == '.') return;
x = x->c[board[i][j]-'a'];
if (! x) return;
if (x->id >= 0) {
ans.push_back(words[x->id]);
x->id = -1;
}
char c = board[i][j];
board[i][j] = '.';
if (i) f(i-1, j, x);
if (j+1 < n) f(i, j+1, x);
if (i+1 < m) f(i+1, j, x);
if (j) f(i, j-1, x);
board[i][j] = c;
}
};