LeetCode() Word Search II

class Solution {
class TrieNode {
public:
// Initialize your data structure here.
TrieNode() {
for(int i=0;i<26;i++)
next[i]=NULL;
isString = false;
}
TrieNode *next[26];
bool isString;
};class Trie {
public:
Trie() {
root = new TrieNode();
} // Inserts a word into the trie.
void insert(string word) {
TrieNode* p=root;
for(int i=0;i<word.size();i++){
if(p->next[word[i]-'a'] == NULL)
p->next[word[i]-'a']=new TrieNode();
p=p->next[word[i]-'a'];
}
p->isString=true; } // Returns if the word is in the trie.
bool search(string word) {
TrieNode* p=root;
for(int i=0;i<word.size();i++){
if(p->next[word[i]-'a'] == NULL) return false;
p=p->next[word[i]-'a'];
}
if(p->isString == true)
return true;
return false;
// return p->isString;
} // Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* p=root;
for(int i=0;i<prefix.size();i++){
if(p->next[prefix[i]-'a'] == NULL) return false;
p=p->next[prefix[i]-'a'];
}
return true;
}private:
TrieNode* root;
};// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
Trie s;
for(auto i:words)
{
if(s.search(i))
{
s.insert(i);
res.push_back(i);
}
else if(exist(board,i))
{
res.push_back(i);
s.insert(i);
}
}
sort(res.begin(),res.end());
return res;
}
bool exist(vector<vector<char>>& board,string word){
for(int i=0;i<board.size();i++)
for(int j=0;j<board[0].size();j++)
if(exist(board,word,i,j,0)) return true;
return false;
}
bool exist(vector<vector<char>>& board,string word,int x,int y,int pos)
{
if(pos == word.size()) return true;
if(x<0 || x>=board.size() || y<0 || y>=board[0].size()) return false;
if(word[pos] == board[x][y])
{
char c=board[x][y];
board[x][y]='#';
bool res=exist(board,word,x+1,y,pos+1)||exist(board,word,x-1,y,pos+1)||exist(board,word,x,y+1,pos+1)||exist(board,word,x,y-1,pos+1);
board[x][y]=c;
return res;
}
return false;
}
};