Word Search II Solutions in C++

// Source : https://leetcode.com/problems/word-search-ii/
// Author : Hao Chen
// Date   : 2015-06-10



const int MAX_CHARS = 26;

class TrieNode {
    public:
        TrieNode(string s):isWord(false), word(s) {
            memset(children, 0, sizeof(children));
        }
        TrieNode* & operator [] (char ch) {
            return children[(ch - 'a') % MAX_CHARS];
        }
        TrieNode* & operator [] (int idx) {
            return children[idx % MAX_CHARS];
        }

    public:
        string word;
        bool isWord;
    private:
        TrieNode* children[MAX_CHARS];
};

class TrieTree {
    public:
        TrieTree():root(new TrieNode("")) { }
        ~TrieTree() { freeTree(root); }
        TrieNode* getRoot() {
            return root;
        }
        void addWord(string& s){
            TrieNode *node = root;
            string t;
            for (int i=0; i<s.size(); i++){
                t += s[i];
                if ( (*node)[s[i]] == NULL ){
                    (*node)[s[i]] = new TrieNode(t);
                }
                node = (*node)[s[i]];
            }
            node->isWord = true;
        }
    private:
        void freeTree(TrieNode* node){
            for(int i=0; i<MAX_CHARS; i++){
                if ((*node)[i]!=NULL){
                    freeTree((*node)[i]);
                }
            }
            delete node;
        }
        TrieNode *root;

};

class Solution {
public:
    void findWords(vector<vector<char>>& board, TrieNode* root, int row, int col, vector<string>& result){
        if (row < 0 || col < 0 || 
                row >= board.size() || 
                col >= board[row].size() ||
                board[row][col] == '\0' ) {
            return;
        }
        
        char ch = board[row][col];
        root = (*root)[ch];
        
        if (root==NULL) return;
        
        if (root->isWord){
            result.push_back(root->word);
            root->isWord = false;
        }
        
        
        board[row][col] = '\0';
        
        findWords(board, root, row, col - 1, result);
        findWords(board, root, row, col + 1, result);
        findWords(board, root, row + 1, col, result);
        findWords(board, root, row - 1, col, result);
        
        board[row][col] = ch;
        
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieTree t;
        for (int i = 0; i<words.size(); i++){
            t.addWord(words[i]);
        }
        
        vector<string> result;
        for (int i = 0; i<board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) { 
                findWords(board, t.getRoot(), i, j, result);
            }
        }
        return result;            
    }

};

/// Source : https://leetcode.com/problems/word-search-ii/
/// Author : liuyubobobo
/// Time   : 2019-02-08

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;


/// Trie + DFS
/// The Trie class is implemented in 208
///
/// Time Complexity: O(4 ^ (m * n) * maxlen)
/// Space Complexity: O(m * n + total_letters_in_words)
class Trie{

private:
    struct Node{
        unordered_map<char, int> next;
        bool end = false;
    };
    vector<Node> trie;

public:
    Trie(){
        trie.clear();
        trie.push_back(Node());
    }

    /** Inserts a word into the trie. */
    void insert(const string& word){

        int treeID = 0;
        for(char c: word){
            if(trie[treeID].next.find(c) == trie[treeID].next.end()){
                trie[treeID].next[c] = trie.size();
                trie.push_back(Node());
            }

            treeID = trie[treeID].next[c];
        }

        trie[treeID].end = true;
    }

    /** Returns if the word is in the trie. */
    bool search(const string& word){

        int treeID = 0;
        for(char c: word){
            if(trie[treeID].next.find(c) == trie[treeID].next.end())
                return false;

            treeID = trie[treeID].next[c];
        }
        return trie[treeID].end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const string& prefix) {

        int treeID = 0;
        for(char c: prefix){
            if(trie[treeID].next.find(c) == trie[treeID].next.end())
                return false;

            treeID = trie[treeID].next[c];
        }
        return true;
    }
};


class Solution {

private:
    int d[4][2] = {{-1, 0}, {0,1}, {1, 0}, {0, -1}};
    int m, n;
    int maxlen = 0;

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

        Trie trie;
        for(const string& word: words){
            trie.insert(word);
            maxlen = max(maxlen, (int)word.size());
        }

        unordered_set<string> res;

        m = board.size();
        assert( m > 0 );
        n = board[0].size();
        for(int i = 0 ; i < m ; i ++)
            for(int j = 0 ; j < n ; j ++){
                vector<vector<bool>> visited(m, vector<bool>(n, false));
                searchWord(board, trie, i, j, "", visited, res);
            }

        return vector<string>(res.begin(), res.end());
    }

private:
    // start from board[x][y], find word s
    void searchWord(const vector<vector<char>> &board, Trie& trie,
                    int x, int y, string s,
                    vector<vector<bool>>& visited, unordered_set<string>& res){

        s += board[x][y];
        if(s.size() > maxlen) return;
        if(!trie.startsWith(s)) return;
        if(trie.search(s)) res.insert(s);

        visited[x][y] = true;
        for(int i = 0 ; i < 4 ; i ++){
            int nextx = x + d[i][0];
            int nexty = y + d[i][1];
            if(inArea(nextx, nexty) && !visited[nextx][nexty])
                searchWord(board, trie, nextx, nexty, s, visited, res);
        }
        visited[x][y] = false;
    }

    bool inArea(int x , int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
};


int main() {

    return 0;
}