TransWikia.com

LeetCode 212: Word Search II

Code Review Asked on November 13, 2021

I’m posting my code for a LeetCode problem. If you’d 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) {
        
    }
};
algorithmbeginnerc++c++17programming challenge

One Answer

Avoid defining trivial constants

While it is good practice to give some constants that are used throughout the code a nice descriptive name, A_LOWERCASE is a case of a trivial constant where it is actually detrimental to define it. The reason is that A_LOWERCASE describes exactly its value, instead of what the value stands for. If you would call it FIRST_LETTER_OF_THE_ALPHABET, it would be a better name (although obviously a bit too long for comfort). But, everyone already knows that 'a' is the first letter. It's as trivial as the numbers 0 and 1, and you wouldn't write:

static constexpr int ZERO = 0;
static constexpr int ONE = 1;

for (int i = ZERO; i < ...; i += ONE) {
    ...
}

Another issue with such constants is that if you ever write constexpr unsigned int A_LOWERCASE = 'b', the compiler won't complain, the code won't work as expected, and someone reading the code will probably not think that A_LOWERCASE might be anything other than 'a' and thus have a hard time finding the issue.

Move TrieNode inside Trie

Since TrieNode is an implementation detail of Trie, it should be moved inside it:

class Trie {
public:
    class Node {
        ...
    };

    Node *get_root() {
        return root;
    }

    ...

private:
    Node *root;
};

Also note that the parent of a tree is not a node. The correct term to use here is "root".

Use std::array to store trie node children

Instead of a fixed size vector, you should use std::array. It avoids a level of indirection:

class Trie {
    class Node {
        std::array<Node *, 26> children;
        ...

Prefer using default member initializers

This avoids having to write a constructor in some cases, and is especially useful to avoid repeating yourself when a class has multiple constructors. In this case you can write:

class Trie {
    class Node {
        std::array<Node *, 26> children{};
        bool is_word{false};
    };
    ...
};

Avoid new when you can just declare a value

In the constructor of Trie you always allocate a new Trie::Node. This is unnecessary, you can just write:

class Trie {
public:
    class Node {...};

    Node *get_root() {
        return &root;
    }

    ...
private:
    Node root;
};

Similarly, in findWords(), you can just write:

std::vector<std::string> findWords(std::vector<std::vector<char>> &board, std::vector<std::string> &words) {
    Trie words;
    ...
}

Use std::unique_ptr to manage memory

Avoid calling new and delete manually. It is easy to make mistakes and cause a memory leak. I don't see any call to delete in your code! A std::unique_ptr will manage memory for you and delete it automatically once it goes out of scope. Here is how to use it:

class Trie {
    class Node {
        std::array<std::unique_ptr<Node>, 26> children;
        ...
    };

    ...

    void set_word(const std::string &word) {
        Node *curr = get_root();

        for (...) {
            ...

            if (!curr->children[index]) {
                curr->children[index] = std::make_unique<Node>();
            }
        
            curr = curr->children[index].get();
         }

         curr->is_word = true;
    }

    ...
};

Prefer using range-for

When iterating over containers (this includes iterating over the characters in a std::string), and you don't need to manipulate the iterator itself but just want to see the values, use a range-for loop. For example in the constructor of Trie:

Trie(const std::vector<std::string> &words) {
    for (auto &word: words) {
        set_word(word);
    }
}

And in set_word():

for (auto letter: word) {
    unsigned int index = letter - 'a';
    ...
}

Simplify return value of findWords()

Instead of creating a temporary std::vector and copying elements manually from found_words, you can make use of the fact that std::vector has a constructor that can copy elements from another container for you, and use brace-initialization in the return statement:

std::vector<std::string> findWords(std::vector<std::vector<char>> &board, std::vector<std::string> &words) {
    std::set<std::string> found_words;
    ...
    return {found_words.begin(), found_words.end()};
}

Answered by G. Sliepen on November 13, 2021

Add your own answers!

Ask a Question

Get help from others!

Recent Answers

Recent Questions

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP