# Leetcode 212 Solution

https://leetcode.com/problems/word-search-ii

## Solution

``````class TrieNode {
public:
TrieNode* m_children[26];

bool m_leaf;

// Initialize your data structure here.
TrieNode() {
m_leaf = false;

for (int i = 0; i < 26; i++)
m_children[i] = 0;
}
};

class Trie {
public:
Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
void insert(string word) {
TrieNode* nextnode = root;

for (int i = 0; i < word.size(); i++)
{
char ch = word[i];

if (nextnode->m_children[ch - 'a'] == NULL)
nextnode->m_children[ch - 'a'] = new TrieNode();

nextnode = nextnode->m_children[ch - 'a'];
}

nextnode->m_leaf = true;
}

// Returns if the word is in the trie.
bool search(string word) {
TrieNode* nextnode = root;

for (int i = 0; i < word.size(); i++)
{
char ch = word[i];

if (nextnode->m_children[ch - 'a'] == NULL)
return false;

nextnode = nextnode->m_children[ch - 'a'];
}

return nextnode->m_leaf;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* nextnode = root;

for (int i = 0; i < prefix.size(); i++)
{
char ch = prefix[i];

if (nextnode->m_children[ch - 'a'] == NULL)
return false;

nextnode = nextnode->m_children[ch - 'a'];
}

return true;
}

TrieNode* root;
};

class Solution {
int m;
int n;

set<string> res;
Trie trie;
public:
void search(vector<vector<char>>& board, int i, int j, string& str, TrieNode* node)
{
char orig = board[i][j];

if (orig == 0)
return;

TrieNode* nextnode = node->m_children[orig - 'a'];
if (nextnode == NULL)
return;

str.push_back(orig);

if (nextnode->m_leaf)
res.insert(str);

board[i][j] = 0;

if (i > 0)
search(board, i - 1, j, str, nextnode);
if (i < m - 1)
search(board, i + 1, j, str, nextnode);
if (j > 0)
search(board, i, j - 1, str, nextnode);
if (j < n - 1)
search(board, i, j + 1, str, nextnode);

board[i][j] = orig;

str.pop_back();
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> vres;
m = board.size();
if (m == 0)
return vres;
n = board[0].size();

for (auto word : words)
trie.insert(word);

for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
string str;
search(board, i, j, str, trie.root);
}

for (auto str : res)
vres.push_back(str);
return vres;
}
};
``````