Leetcode 212 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;
    }
};