# C++ 462 ms brute force and 35 ms Trie solution

• Solution 1

Brute force. Using solution of Word Search.
Runime: 462 ms

``````class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string>res;
unordered_map<char, vector<string>>m;
for(auto x: words) m[x[0]].push_back(x);
for(int i = 0; i < board.size(); i++)
for(int j = 0; j < board[0].size(); j++)
if(m[board[i][j]].size() > 0)
for(auto x: m[board[i][j]]){
bool found = false;
backtrack(board, 1, i, j, board.size(), board[0].size(), x, found);
if(found && find(res.begin(), res.end(), x) == res.end()) res.push_back(x);
}
return res;
}

void backtrack(vector<vector<char>>& board, int pos, int r, int c, int m, int n, string& word, bool& found){
if(board[r][c] == '0' || found) return;
if(pos == word.size()){
found = true;
return;
}
char tmp = board[r][c];
board[r][c] = '0';
if(r - 1 >= 0 && board[r - 1][c] == word[pos]) backtrack(board, pos + 1, r - 1, c, m, n, word, found);
if(r + 1 < m  && board[r + 1][c] == word[pos]) backtrack(board, pos + 1, r + 1, c, m, n, word, found);
if(c + 1 < n  && board[r][c + 1] == word[pos]) backtrack(board, pos + 1, r, c + 1, m, n, word, found);
if(c - 1 >= 0 && board[r][c - 1] == word[pos]) backtrack(board, pos + 1, r, c - 1, m, n, word, found);
board[r][c] = tmp;
}
};
``````

Solution 2

Runtime: 35 ms. (Beats 95.58% of C++ solutions.)

``````struct TrieNode{
string word;
TrieNode* next[26];
};

class Solution {
private:
TrieNode* root;
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string>res;
buildTrie(words);
for(int i = 0; i < board.size(); i++)
for(int j = 0; j < board[0].size(); j++)
backtrack(board, res, i, j, board.size() - 1, board[0].size() - 1, root);
return res;
}

void backtrack(vector<vector<char>>& board, vector<string>& res, int r, int c, int m, int n, TrieNode* p){
if(r < 0 || c < 0 || r > m || c > n || board[r][c] == '0'|| !p->next[board[r][c] - 'a']) return;
p = p->next[board[r][c] - 'a'];
if(p->word.size() > 0){
res.push_back(p->word);
p->word = "";
}
char tmp = board[r][c];
board[r][c] = '0';
backtrack(board, res, r - 1, c, m, n, p);
backtrack(board, res, r + 1, c, m, n, p);
backtrack(board, res, r, c + 1, m, n, p);
backtrack(board, res, r, c - 1, m, n, p);
board[r][c] = tmp;
}

void buildTrie(vector<string>& words){
root = new TrieNode();
for(auto x: words){
TrieNode* p = root;
for(auto c: x){
if(!p->next[c - 'a']) p->next[c - 'a'] = new TrieNode();
p = p->next[c - 'a'];
}
p->word = x;
}
}
};
``````

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