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;

    }

};