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
| #define MAXN 10001
class Solution {
public:
int tree[MAXN][26] = {};
int passed[MAXN] = {};
string end[MAXN] = {};
int cnt = 1;
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
build(words);
vector<string> ans;
for(int i=0; i<board.size(); ++i)
for(int j=0; j<board[0].size(); ++j)
dfs(board, i, j, 1, ans);
clear();
return ans;
}
int dfs(vector<vector<char>>& board, int i, int j, int curr, vector<string>& ans){
if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == 0) return 0;
char tmp = board[i][j];
int path = tmp - 'a';
curr = tree[curr][path];
if(passed[curr] == 0) return 0;
int collected = 0;
if(end[curr] != ""){
ans.push_back(end[curr]);
collected++;
end[curr] = "";
}
board[i][j] = 0;
collected += dfs(board, i + 1, j, curr, ans);
collected += dfs(board, i - 1, j, curr, ans);
collected += dfs(board, i, j + 1, curr, ans);
collected += dfs(board, i, j - 1, curr, ans);
board[i][j] = tmp;
passed[curr] -= collected;
return collected;
}
void build(vector<string>& words){
cnt = 1;
for(string word : words){
int curr = 1;
passed[curr]++;
for(int i=0, path; i<word.length(); ++i){
path = word[i] - 'a';
if(tree[curr][path] == 0) tree[curr][path] = ++cnt;
curr = tree[curr][path];
passed[curr]++;
}
end[curr] = word;
}
}
void clear(){
for(int i=1; i<=cnt; ++i){
for(int j=0; j<26; ++j){
tree[i][j] = 0;
}
passed[i] = 0;
end[i] = "";
}
cnt = 1;
}
};
|
