LeetCode 212: Word Search II

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input:  board = [   
['o','a','a','n'],   
['e','t','a','e'],  
['i','h','k','r'],   
['i','f','l','v'] 
] 
words =
["oath","pea","eat","rain"]

Output: ["eat","oath"] 

Note:

• All inputs are consist of lowercase letters a-z.
• The values of words are distinct.

Code

#include <vector>
#include <string>
#include <set>

class Solution {
    static constexpr unsigned int A_LOWERCASE = 'a';
    static constexpr unsigned int ALPHABET_SIZE = 26;

private:
    class TrieNode {
    public:
        std::vector<TrieNode *> children;
        bool is_word;

        TrieNode() {
            is_word = false;
            children = std::vector<TrieNode *>(ALPHABET_SIZE, NULL);
        }
    };

    class Trie {
    public:
        TrieNode *get_parent() {
            return parent;
        }

        Trie(const std::vector<std::string> &words) {
            parent = new TrieNode();

            for (unsigned int index = 0; index < words.size(); index++) {
                set_word(words[index]);
            }
        }

        void set_word(const std::string &word) {
            TrieNode *curr = parent;

            for (unsigned int length = 0; length < word.size(); length++) {
                unsigned int index = word[length] - A_LOWERCASE;

                if (curr->children[index] == NULL) {
                    curr->children[index] = new TrieNode();
                }

                curr = curr->children[index];
            }

            curr->is_word = true;
        }

    private:
        TrieNode *parent;

    };

public:
    std::vector<std::string> findWords(std::vector<std::vector<char>> &board, std::vector<std::string> &words) {
        Trie *trie = new Trie(words);
        TrieNode *parent = trie->get_parent();
        std::set<std::string> found_words;

        for (unsigned int row = 0; row < board.size(); row++) {
            for (unsigned int col = 0; col < board[0].size(); col++) {
                depth_first_search(board, row, col, parent, "", found_words);
            }
        }

        std::vector<std::string> structured_found_words;

        for (const auto found_word : found_words) {
            structured_found_words.push_back(found_word);
        }

        return structured_found_words;
    }

private:

    static void depth_first_search(std::vector<std::vector<char>> &board, const unsigned int row, const unsigned int col, const TrieNode *parent, std::string word, std::set<std::string> &structured_found_words) {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] == ' ') {
            return;
        }

        if (parent->children[board[row][col] - A_LOWERCASE] != NULL) {
            word = word + board[row][col];
            parent = parent->children[board[row][col] - A_LOWERCASE];

            if (parent->is_word) {
                structured_found_words.insert(word);
            }

            char alphabet = board[row][col];
            board[row][col] = ' ';
            depth_first_search(board, row + 1, col, parent, word, structured_found_words);
            depth_first_search(board, row - 1, col, parent, word, structured_found_words);
            depth_first_search(board, row, col + 1, parent, word, structured_found_words);
            depth_first_search(board, row, col - 1, parent, word, structured_found_words);
            board[row][col] = alphabet;
        }
    };
};

Reference

LeetCode has a template for answering questions. There is usually a class named Solution with one or more public functions which we are not allowed to rename. For this question, the template is:

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        
    }
};

• Problem

• Solution

• Discuss

• Trie