Function dfs

cpp/Tries/find_all_words_on_a_board.cpp:47–71

}

void dfs(std::vector<std::vector<char>>& board, int r, int c, TrieNode* node, std::vector<std::string>& res) {
    // If the current node represents the end of a word, add the word to
    // the result.
    if (!node->word.empty()) {
        res.push_back(node->word);
        // Ensure the current word is only added once.
        node->word = "";
    }
    char temp = board[r][c];
    // Mark the current cell as visited.
    board[r][c] = '#';
    // Explore all adjacent cells that correspond with a child of the 
    // current TrieNode.
    std::vector<std::pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    for (auto& dir : dirs) {
        int next_r = r + dir.first;
        int next_c = c + dir.second;
        if (isWithinBounds(next_r, next_c, board) &&
            node->children.find(board[next_r][next_c]) != node->children.end()) {
            dfs(board, next_r, next_c, node->children[board[next_r][next_c]], res);
        }
    }
    // Backtrack by reverting the cell back to its original character.
    board[r][c] = temp;
}

bool isWithinBounds(int r, int c, std::vector<std::vector<char>>& board) {
    return r >= 0 && r < board.size() && c >= 0 && c < board[0].size();