### LeetCode June Challenge - Day 30

Problem: LeetCode June Challenge - Day 30

Ideas

1. Backtracking. I used recursion to make it easier to implement.
2. I use the Trie I implemented for another daily task, with one modification, it now deletes a word after finding it, preventing me from pushing duplicates to the answer.

Solution:

``````class Node {
private:
Node* l['z'-'a'+1];
bool end;
public:
Node(){
end = false;
memset(l,0,sizeof(l));
}
void mark(){
end = true;
}
void unmark(){
end = false;
}
bool is_marked(){
return end;
}
Node* insert(char c){
if(l[c-'a'] == NULL)
l[c-'a'] = new Node();
return l[c-'a'];
}
Node* get(char c){
return l[c-'a'];
}
};

class Trie {
Node* root;
public:
/** Initialize your data structure here. */
Trie() {
root = new Node();
}

/** Inserts a word into the trie. */
void insert(string& word) {
Node* it = root;
for(char c : word){
it = it->insert(c);
}
it->mark();
}

/** Returns if the word is in the trie. */
bool search(string& word) {
Node* it = root;
for(char c : word){
it = it->get(c);
if(it == NULL) return false;
}
if(it->is_marked()){
it->unmark();
return true;
}
return false;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Node* it = root;
for(char c : prefix){
it = it->get(c);
if(it == NULL) return false;
}
return true;
}
};

class Solution {
int n, m;
Trie* t;
string current;
vector<string> ans;
bool visited[30][30];

void recursion(int i, int j, vector<vector<char>>& board){
current.push_back(board[i][j]);
if(t->startsWith(current)){
if(t->search(current))
ans.push_back(current);
visited[i][j] = true;
if(i > 0 && !visited[i-1][j])
recursion(i-1, j, board);
if(i < n-1 && !visited[i+1][j])
recursion(i+1, j, board);
if(j > 0 && !visited[i][j-1])
recursion(i, j-1, board);
if(j < m-1 && !visited[i][j+1])
recursion(i, j+1, board);
visited[i][j] = false;
}
current.pop_back();
}

public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
if(board.empty() || board[0].empty())
return vector<string>();

t = new Trie();
memset(visited, 0, sizeof(visited));
for(string s : words) t->insert(s);
current = "";
n = board.size(), m = board[0].size();

for(int i=0; i<board.size(); ++i)
for(int j=0; j<board[i].size(); ++j)
recursion(i,j, board);
return ans;
}
};
``````