My initial idea is to use dfs for each character in the board. And for each dfs, we search the word so far in the dictionary. The dictionary is a hash table built by the input vector words. However, by the idea of trie, it'll be much faster than hash table. Note, to avoid duplicates, I use the set instead of array to hold the results.
1: class TrieNode {
2: public:
3: TrieNode *next[26];
4: bool isEnd;
5: TrieNode() {
6: memset(next, 0, sizeof(next));
7: isEnd = false;
8: }
9: };
10: class Trie {
11: public:
12: TrieNode *next[26];
13: bool isEnd;
14: Trie (vector<string> &words) {
15: root = new TrieNode();
16: for (int i = 0; i < words.size(); i++) {
17: _insert(words[i]);
18: }
19: }
20: TrieNode *getRoot() {
21: return root;
22: }
23: private:
24: TrieNode *root;
25: void _insert(string word) {
26: TrieNode *p = root;
27: for (int i = 0; i < word.size(); i++) {
28: if (p->next[word[i]-'a'] == NULL) {
29: p->next[word[i]-'a'] = new TrieNode();
30: }
31: p = p->next[word[i]-'a'];
32: }
33: p->isEnd = true;
34: }
35: };
36: class Solution {
37: public:
38: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
39: Trie *trie = new Trie(words);
40: TrieNode *root = trie->getRoot();
41: unordered_set<string> res;
42: string sol;
43: for (int i = 0; i < board.size(); i++) {
44: for (int j = 0; j < board[0].size(); j++) {
45: find(board, i, j, root, sol, res);
46: }
47: }
48: return vector<string>(res.begin(), res.end());;
49: }
50: void find(vector<vector<char>> &board, int i, int j, TrieNode *t, string sol, unordered_set<string> &res) {
51: if (i < 0 || j < 0 || i == board.size() || j == board[0].size() || board[i][j] == 0) return;
52: if (t->next[board[i][j]-'a'] != NULL) {
53: sol += board[i][j];
54: t = t->next[board[i][j]-'a'];
55: if (t->isEnd) res.insert(sol);
56: char c = board[i][j];
57: board[i][j] = 0;
58: find(board, i+1, j, t, sol, res);
59: find(board, i-1, j, t, sol, res);
60: find(board, i, j+1, t, sol, res);
61: find(board, i, j-1, t, sol, res);
62: board[i][j] = c;
63: }
64: }
65: };
When I revisited this problem, I had following solution which has the same idea. I made mistakes in,
line 20: I put this line into the if clause which misses the case when the next trie node isn't null.
line 54: I was using vector first but it will include some duplicates. So I changed it to set.
line 56-58: First of all, I had line 58 before line 56-57. This results in empty output. Then, I realized that line 58 should check after we've include the new trie node (because the root in dfs() function is the parent node trie node). However, the result missed last node in a word. Then I eventually moved line 58 behind line 56-57 and get the correct result.
Also it is very easy to make mistake in
line 65 to pass "root->next[board[i][j]-'a']" to the dfs function. Note at that moment, board[i][j] has been changed to 0 so you'll get segment fault.
1: class TrieNode {
2: public:
3: bool isEnd;
4: vector<TrieNode *> next;
5: TrieNode() {
6: isEnd = false;
7: next = vector<TrieNode *>(26, NULL);
8: }
9: };
10: class Trie {
11: private:
12: TrieNode *root;
13: void _insert(string word) {
14: TrieNode *p = root;
15: for (int i = 0; i < word.size(); i++) {
16: int index = word[i]-'a';
17: if (p->next[index] == NULL) {
18: p->next[index] = new TrieNode();
19: }
20: p = p->next[index];
21: }
22: p->isEnd = true;
23: }
24: public:
25: Trie(vector<string> &words) {
26: root = new TrieNode();
27: for (int i = 0; i <words.size(); i++) {
28: _insert(words[i]);
29: }
30: }
31: TrieNode *getRoot() {
32: return root;
33: }
34: };
35: class Solution {
36: private:
37: int row, col;
38: vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
39: public:
40: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
41: set<string> res;
42: row = board.size();
43: if (row == 0) return vector<string>();
44: col = board[0].size();
45: Trie *trie = new Trie(words);
46: TrieNode *root = trie->getRoot();
47: for (int i = 0; i < row; i++) {
48: for (int j = 0; j < col; j++) {
49: dfs(board, i, j, root, "", res);
50: }
51: }
52: return vector<string>(res.begin(), res.end());
53: }
54: void dfs(vector<vector<char>> &board, int i, int j, TrieNode *root, string path, set<string> &res) {
55: if (root->next[board[i][j]-'a'] == NULL) return;
56: root = root->next[board[i][j]-'a'];
57: path += board[i][j];
58: if (root->isEnd) res.insert(path);
59: char c = board[i][j];
60: board[i][j] = 0;
61: for (int d = 0; d < dir.size(); d++) {
62: int ii = i + dir[d].first;
63: int jj = j + dir[d].second;
64: if (ii < 0 || ii == row || jj < 0 || jj == col || board[ii][jj] == 0) continue;
65: dfs(board, ii, jj, root, path, res);
66: }
67: board[i][j] = c;
68: }
69: };
