struct Trie {
    Trie() : word(false), parent(nullptr), children(26) {}

    ~Trie() {
        for (Trie *n : children)
            delete n;
    }

    void add(const string &s, int pos=0) {
        if (pos == s.length())
            word = true;
        else {
            int code = to_code(s[pos]);
            if (code == -1) {
                // could skip ?
                //add(s, pos + 1);
                ostringstream out;
                out << "bad char at " << pos << ": s";
                throw runtime_error(out.str());
            } else {
                if (!children[code]) {
                    children[code] = new Trie;
                    children[code]->parent = this;
                }
                children[code]->add(s, pos + 1);
            }
        }
    }
    
    void remove() {
        if (!word) return;
        word = false;
        
        for (Trie *child : children) {
            if (child)
                return;  
        }
        
        // not any child; detach from parent if there is one
        if (parent)
            parent->detach(this);
        delete this;
    }

    Trie *next(char c) {
        return children[to_code(c)];
    }

    bool word;
    Trie *parent;
    vector<Trie *> children;

private:
    static int to_code(char c) {
        return ('A' <= c && c <= 'Z') ? c - 'A' :
            ('a' <= c && c <= 'z') ? c - 'a' :
            -1;
    }
    
    void detach(Trie *child) {
        bool any_child = false;
        for (int i = 0; i < children.size(); i++) {
            if (children[i]) {
                if (children[i] == child)
                    children[i] = nullptr;
                else
                    any_child = true;
            }
        }
        
        /*
         * XXX This doesn't work if too much is removed.
         * Tombstoning would work, though.
         * Flag for deletion, then the recursion caller checks if it's been deleted yet.
         *
         * // not any child; detach from parent if there is one
         * if (!any_child && parent) {
         *     parent->detach(this);
         *     delete this;
         * }
         */
    }
};

class Solution {
public:
    vector<string> findWords(const vector<vector<char>> &board, const vector<string> &words) {
        return find_words_TRIE(board, words);
        //return find_words_RANGE(board, words);
    }
    
    /*
     * RANGE-BASED SOLUTION
     */
    
    vector<string> find_words_RANGE(
        const vector<vector<char>> &board, vector<string> words
    ) {
        sort(words.begin(), words.end());
        
        vector<vector<uint8_t>> visited(board.size(), vector<uint8_t>(board[0].size()));
        string word;
        
        unordered_set<string> found;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                find_words_from_RANGE(
                    board, words, visited, word, {i, j}, {0, words.size()}, found
                );
            }
        }
        vector<string> out(found.begin(), found.end());
        sort(out.begin(), out.end());
        return out;
    }
    
    pair<int, int> sub_range(
        const vector<string> &words, pair<int, int> range, char ch, int pos
    ) {
        auto [lo, hi] = range;
        
        // find lower_bound
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (words[mid][pos] < ch)
                lo = mid + 1;
            else
                hi = mid;
        }
        int lower = lo;
        
        // find upper_bound
        hi = range.second;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (words[mid][pos] <= ch)
                lo = mid + 1;
            else
                hi = mid;
        }
        int upper = hi;
        return {lower, upper};
    }
    
    void find_words_from_RANGE(
        const vector<vector<char>> &board,
        const vector<string> &words,
        // state of recursion
        vector<vector<uint8_t>> &visited,
        string &word,
        pair<int, int> loc,
        pair<int, int> prev_range,
        // output
        unordered_set<string> &out
    ) {
        // visit loc
        char ch = board[loc.first][loc.second];
        pair<int, int> range = sub_range(words, prev_range, ch, word.length());
        if (range.first == range.second)
            return;
        
        visited[loc.first][loc.second] = 1;
        word += ch;
        for (int r = loc.first - 1; r < loc.first + 2; r++) {
            if (r < 0 || r >= board.size())
                continue;
            for (int c = loc.second - 1; c < loc.second + 2; c++) {
                if (c < 0 || c >= board[r].size())
                    continue;
                // don't allow repeats or [r,c]==loc
                if (visited[r][c])
                    continue;
                // no diagonals:
                if (r != loc.first && c != loc.second)
                    continue;
                find_words_from_RANGE(
                    board, words,
                    visited, word, {r, c}, range,
                    out
                );
            }
        }
        if (words[range.first].length() == word.length())
            out.insert(word);
        word.erase(word.length() - 1);
        visited[loc.first][loc.second] = 0;
    }
    
    /*
     * TRIE-BASED SOLUTION
     */
    
    vector<string> find_words_TRIE(
        const vector<vector<char>>& board, const vector<string>& words
    ) {
        Trie dict;
        for (auto &word : words)
            dict.add(word);
        
        vector<vector<uint8_t>> visited(board.size(), vector<uint8_t>(board[0].size()));
        string word;
        
        vector<string> out;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                find_words_from_TRIE(
                    board,
                    visited, word, {i, j}, &dict,
                    out
                );
            }
        }
        sort(out.begin(), out.end());
        return out;
    }
    
    void find_words_from_TRIE(
        const vector<vector<char>> &board,
        // state of recursion
        vector<vector<uint8_t>> &visited,
        string &word,
        pair<int, int> loc,
        Trie *prev_cursor,
        // output
        vector<string> &out
    ) {
        // visit loc
        char ch = board[loc.first][loc.second];
        Trie *cursor = prev_cursor->next(ch);
        if (!cursor)
            return;
        
        visited[loc.first][loc.second] = 1;
        word += ch;
        for (int r = loc.first - 1; r < loc.first + 2; r++) {
            if (r < 0 || r >= board.size())
                continue;
            for (int c = loc.second - 1; c < loc.second + 2; c++) {
                if (c < 0 || c >= board[r].size())
                    continue;
                // don't allow repeats or [r,c]==loc
                if (visited[r][c])
                    continue;
                // no diagonals:
                if (r != loc.first && c != loc.second)
                    continue;
                find_words_from_TRIE(board, visited, word, {r, c}, cursor, out);
            }
        }
        if (cursor->word) {
            out.push_back(word);
            //cursor->word = false;
            cursor->remove();
        }
        word.erase(word.length() - 1);
        visited[loc.first][loc.second] = 0;
    }
};