# C++ Simple Solution, Trie, Backtrace, DFS

• ``````class Solution {
private:
class Node {
public:
char c;
string word;
Node* next[26];
Node(char c = '.') : c(c) {
fill_n(next, 26, nullptr);
}
~Node() {
for (auto& i : next)
delete i;
}
};

void dfs(Node* cur, vector<vector<char>>& board, vector<string>& res, int r, int c) {
char def = board[r][c];
board[r][c] = '\0';
int m = board.size(), n = board[0].size();
if (cur->word.size() && mp.find(cur->word) == mp.end()) {
res.push_back(cur->word);
mp[cur->word] = true;
}
vector<pair<int, int>> nei = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto i : nei) {
int rr = r + i.first, cc = c + i.second;
if (rr < 0 || rr >= m || cc < 0 || cc >= n || board[rr][cc] == '\0' ||
cur->next[board[rr][cc] - 'a'] == nullptr)
continue;
dfs(cur->next[board[rr][cc] - 'a'], board, res, rr, cc);
}
board[r][c] = def;
}

unordered_map<string, bool> mp;
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
int m = board.size(), n = m ? board[0].size() : 0;
vector<string> res;
Node* root = new Node();
for (auto& word : words) {
Node* cur = root;
for (auto c : word) {
if (cur->next[c - 'a'] == nullptr) {
cur->next[c - 'a'] = new Node(c);
}
cur = cur->next[c - 'a'];
}
cur->word = word;
}

for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (root->next[board[i][j] - 'a'])
dfs(root->next[board[i][j] - 'a'], board, res, i, j);
delete root;
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.