Coding style and idiomaticity of solution to the Word Search II problem on LeetCode

Question

"Word Search II" is a hard problem on LeetCode (problem #212):

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

The following solution of mine passes all the tests. I would very much appreciate comments as to how I can improve on the coding style and idiomatic use of C++.

struct TrieNode {
    bool endFlag = false;
    // The pointer has to be shared.
    // Otherwise deletion of words may invalidate pointers in the caller.
    unordered_map<char, shared_ptr<TrieNode>> children;
    
    shared_ptr<TrieNode> getChild(char c) {
        auto it = children.find(c);
        return (it != children.end()) ? it->second : nullptr;
    }

    TrieNode *addChild(char c) {
        TrieNode *res = new TrieNode;
        children.insert(make_pair(c, shared_ptr<TrieNode>(res)));
        return res;
    }
};

struct Trie {
    TrieNode head;
    
    void insert(const string &s) {
        TrieNode *cur = &head;
        for (char c: s) {
            TrieNode *next = (cur->getChild(c)).get();
            if (!next) next = cur->addChild(c);
            cur = next;
        }
        cur->endFlag = true;
    }
    
    void erase(const string &s) {
        erase(&head, s, 0);
    }
    
    // For debugging
    void dump() {
        cout << endl << endl << "DUMPING THE TRIE" << endl;
        dump(&head, 0);
    }
private: 
    // Return whether there are words below node;
    bool erase(TrieNode *node, const string &s, int i) {
        if (i == s.size())
            node->endFlag = false;
        else {
            bool res = erase((node->getChild(s[i])).get(), s, i + 1);
            if (!res) (node->children).erase(s[i]);
        }
        return (node->children).size()  || node->endFlag;
    }
    
    // For debugging
    void dump(TrieNode *node, int depth) {
        string indent(4 * depth, ' ');
        if (node->endFlag) cout << indent << "END" << endl;
        for (char c = 'a'; c <= 'z'; ++c) {
            TrieNode *child = (node->getChild(c)).get();
            if (child) {
                cout << indent << c << endl;
                dump(child, depth + 1);
            }
        }    
    }
};


class Solution {
    int m, n;
    unordered_set<string> res;
    Trie trie;
    
    void buildTrie(const vector<string> &words) {
        for (const auto &w: words)
            trie.insert(w);
    }
    
    string stackToWord(const vector<vector<char>>& board, 
                      vector<vector<int>> &stack) {
        string res;
        for (const auto &loc: stack)
            res += board[loc[0]][loc[1]];
        return res;
    }
    
    void search
        (const vector<vector<char>>& board, 
         const vector<int> &loc, 
         vector<vector<int>> &stack,
         TrieNode *trieNode) {
        if (trieNode->endFlag) {
            string word = stackToWord(board, stack);
            res.insert(word);
            trie.erase(word); 
        }
        
        int r = loc[0], c = loc[1];
        if (r < 0 || r > m - 1) return;
        if (c < 0 || c > n - 1) return;
        if (find(stack.begin(), stack.end(), loc) != stack.end())
            return;
        
        shared_ptr<TrieNode>child = trieNode->getChild(board[r][c]);
        if (!child) return;
        
        stack.push_back(loc);
        search(board, {r + 1, c}, stack, child.get());
        search(board, {r - 1, c}, stack, child.get());
        search(board, {r, c + 1}, stack, child.get());
        search(board, {r, c - 1}, stack, child.get());
        stack.pop_back();
    }
    
public:    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        buildTrie(words);
        m = board.size();
        n = board[0].size();
        
        vector<vector<int>> stack;
        for (int r = 0; r < m; ++r)
            for (int c = 0; c < n; ++c)
                search(board, {r, c}, stack, &trie.head);
                    
        return vector<string>(res.begin(), res.end());
    }
};
```

Answer 1

Use full names

First of all, don't use arbitary abbreviations: HTTP is fine, it's well known and "domain knowledge", res isn't. It takes very little effort to use result instead, just type it in full.

Naming is difficult, but good naming makes code incredibly clearer. It's a skill worth polishing, and time well spent.

Create meaningful types

What is a std::vector<std::vector<char>>? A list of words? Something else?

The main issue with issue an all-purpose type directly is that it can represent anything and it can do anything, even operations that would be wild.

A type is all of:

• A name, the who.
• A set of invariants on the values it can take, the what.
• A collection of operations, the how.

It is important to fully think out the invariants and the operations:

• What does it mean for a board to be "unbalanced"? That is, having 2 rows of different length? Should that be allowed?
• What does it mean, then, to erase a character in a row? Should that be allowed?
• Should reordering the rows be allowed?

Ideally, you want to ensure that:

• A 100% valid/representable ratio for the set of values.
• A 100% meaningful/possible ratio for the set of operations.

I advise naming first, and setting them some representation of the state to get started. If well encapsulated, you can change it easily enough after all:

class Board {
public:
    // I generally recommend public first; it's the API after all.

private:
    std::vector<std::vector<char>> colums;
};

struct Dimensions {
    int rows = 0;
    int columns = 0;
};

struct Position {
    int x = 0;
    int y = 0;
};

This sets you up to write better code.

Note: I do not particularly endorse the std::vector<std::vector<char>> representation but... it doesn't matter. Now that it's private it can be changed at leisure without any impact on existing clients!

And with regard to API, let's start with a streaming operator to be able to print... everything.

bool operator<<(std::ostream& out, Position const& position);

Then let's review what we need of the board:

 class Board {
 public:
     //  As supplied by LeetCode.
     explicit Board(std::vector<std::vector<char>> const& board);

     Dimensions get_dimensions() const noexcept;

     //  Throws on positions out of bounds.
     char operator[](Position position) const;

 private:
     // ...
 };

This means we can talk about Position:

bool operator==(Position const& left, Position const& right) noexcept;

bool operator!=(Position const& left, Position const& right) noexcept;

Adding equality should generally be seen as a trigger to consider hashing, so let's:

template <>
struct std::hash<Position> {
    std::size_t operator()(Position const& position) const;
};

And it'd be nice to have a way to check whether a Position is within the bounds of the board:

bool is_within(Position const& position, Dimensions const& dimensions);

That sets up nicely.

Encapsulate, encapsulate, encapsulate.

Some types, like Position and Dimensions, do not really have much in the sense of invariants (though negative dimensions should raise an eyebrow), so having them as struct is fine.

On the other hand, types like a Trie do maintain complex invariants; for example your Trie is pruning the nodes it no longer needs. Those should be well encapsulated:

• Members should be private.
• And mutable references to them should not be exposed.

Encapsulation is also nice to reduce dependencies, such as the inner representation of Board which can be changed at will.

So... let's rethink Trie:

class Trie {
public:
    class Node {
    public:
        // We'll come back later
    private:
        bool endWord = false;
        std::unordered_map<char, Node> children;
    };

    //  We'll come back later
private:
    Node root;
};

Now, the operations:

 //  Of course!
 std::ostream& operator<<(std::ostream& out, Trie const& trie);

We'll need to iterate over the Trie, as well as insert and remove words from it:

 class Trie {
 public:
     Node const* root() const;

     void insert(std::string_view word);

     void remove(std::string_view word);

 private:
     // ...
 };

And the same for Node, really.

 class Node {
 public:
      Node const* get_child(char c) const;

      void insert(std::string_view suffix);

      void remove(std::string_view suffix);

 private:
     // ...
 };

Do note how I "raised the level" of the operations, from talking about nitty gritty details (getChild/addChild) to talking about the problem domain. In general, it's a win, as it encapsulates implementation details.

Lifetime of Nodes

As you noted, there's a lifetime issue: what if a node is removed that is still referenced?

You solved it by std::shared_ptr which works, though it's expensive and verbose.

In this particular problem, however, you didn't need to. That is, you can separate the logical concept of removing a word from the Trie and the implementation concern of removing a node from the Trie. You're starting with a fixed list of words, after all, so there won't be unbounded growth.

The lifetime problem can therefore be fixed, cheaply, by simply moving the node to a deleted list.

class Node {
public:
    //  As above.
private:
    using Children = std::unordered_map<char, Node>;

    bool endWord = false;
    Children children;
    std::vector<Children::node_type> deleted_children;
};

node_type comes from C++17's extract method; very useful to avoid allocating separately:

• The node still exists, though outside the container so that find, or iteration do not see it.
• All iterators to it are invalidated, but pointers and references are not.

You can also merge it back into this container (or another) but that won't be of use here.

Don't Repeat Yourself.

This is painful to write, and to read:

search(board, {r + 1, c}, stack, child.get());
search(board, {r - 1, c}, stack, child.get());
search(board, {r, c + 1}, stack, child.get());
search(board, {r, c - 1}, stack, child.get());

Hopefully the only difference are the coordinates...

Instead imagine:

for (Direction direction : { Down, Up, Right, Left }) {
    search(board, position.next(direction), stack, child);
}

Isn't it much clearer?

Or you could go with:

std::array<Position; 4> get_neighbours(Position p) {
    return {{ { p.x + 1, p.y }, { p.x - 1, p.y }
              { p.x, p.y + 1 }, { p.x, p.y - 1 } }};
}

for (auto neighbour : get_neighbours(loc)) {
    search(board, neighbour, stack, child);
}

It has the advantage of avoiding to forget a neighbour in the list, and since the directions are not otherwise used, that may be good enough without introducing a long-ish next method.

Anything but copy/pasting mostly identical lines of code is better, really.

---

With regard to the algorithmic details:

I'm somewhat concerned about the algorithmic complexity of that std::find(stack.begin(), stack.end(), loc) call. Your stack can get as long as the longer word (or close to), so we're talking O(L) for each individual call, and it's called within a recursion called within the inner loop. Sounds like a recipe for quadratic complexity in the inner loop; best avoided. It may be worth keeping a std::hash_set<Position> instead to get O(1).¹

Similarly, it may be worth eliminating impossible words from the get go. Since you can't reuse any board cell within a given word, doing a quick count of the number of occurrences of each character on the board and comparing it to a quick count for each word would eliminate the words that cannot possibly be on the board very cheaply. I'd suggest doing it even before creating the Trie. Bonus: it automatically eliminates words longer than the number of cells of the board; a nice way to introduce terrible complexity in your current algorithm....

¹ I'd create a Path class containing the set of Positions and a string equal to the sequence of characters seen so far with add(Position, Board const&) and remove(Position, Board const&) methods. As a bonus, you can remove stackToWord.

---

With regard to the nitpicky details:

1. Write tests.
   • Yes, I know that you can't submit them. Write them anyway, in a separate file, and compile and run locally to check your edge cases.
   • And also check performance edge cases; like... a 8x8 board with a square of 7x7 As (upper left), then an A in bottom right, and the rest all Bs, with a word being 50 As: is it much slower than usual 8x8 boards?
2. Don't hardcode cout, that's what operator<< is for:
   • It allows bundling additional detail on the line.
   • It instantly becomes trivial to write a test for that code too; it's nice to ensure debug code works, if you can't rely on it, how are you going to debug the rest? Don't want to go chasing gooses!
3. Always use {} around blocks, even when the grammar allows omitting it such as after if.
   • Search for GOTO FAIL to learn how blocks can save the day...

Answer 2

LeetCode vs. proper C++

The LeetCode site teaches some bad coding habits that you should try to avoid. In particular:

• There is no need for a class Solution, in proper C++ code you would write a free function findWords(), possibly with some helper functions that are declared static or put in an anonymous namespace. To avoid using global variables, this require passing more parameters to those functions, but I think that is fine here. If you would need a lot of state you could create a struct to hold that state, and a reference to that struct to the helper functions. This struct would not have to be visible to the user of findWords().
• Vectors of vectors are inefficient datastructures; not only do they use a bit more memory, they also don't guarantee that data is layed out contiguously in memory, and there is more pointer indirection needed to access elements, leading to slower performance. The typical solution is to use a flat std::vector that you index using column + row * width.
• Reference parameters that are not modified should be declared const.
• Use std:: in your code instead of using using namespace std. This is especially important if you ever move struct Trie to a header file for example.
• If you did #include <bits/stdc++.h>, don't.

You might need to do some of these things to pass some automated checker on LeetCode, but it is better to not do these things in a job interview.

Move TrieNode into Trie

A TrieNode is a data structure specifically to be used inside of a Trie. You can make this relation more clear, and make the name shorter at the same time, by declaring it inside the declaration of Trie:

struct Trie {
    struct Node {
         ...
    };

    Node head;
    ...
};

...

void search(const vector<vector<char>>& board, 
            const vector<int>& loc, 
            vector<vector<int>>& stack,
            Trie::Node* trieNode) {
    ...
}

Use '\n' instead of std::endl

u19G; the latter is equivalent to the former, but forces the output to be flushed, which is usually not necessary and has a negative impact on performance.

Avoid manual new and delete

Smart pointers help you avoid using new and delete. However, memory still needs to be allocated for objects that are held by a std::shared_ptr. To avoid having to use new for that, use std::make_shared(). You could do it like this:

Node* addChild(char c) {
    auto nodePtr = std::make_shared<Node>();
    children[c] = nodePtr;
    return nodePtr.get();
}

But it is a bit nasty; there is more than one std::shared_ptr in that piece of code, so there is unnecessary overhead. You can avoid a copy by writing:

Node* addChild(char c) {
    return (children[c] = std::make_shared<Node>()).get();
}

It might look like it still does the same, but because we didn't create a named variable nodePtr here, the std::shared_ptr<Node> we create here is a temporary obect, and std::unordered_map::operator=() has an overload that will use move-assignment to move ownership of the Node object from the temporary to children[c].

Or perhaps return a reference to a std::shared_ptr to let the caller deal with performing the .get():

std::shared_ptr<Node>& addChild(char c) {
    return children[c] = std::make_shared<Node>();
}

But we can avoid this whole problem altogether:

Don't use std::shared_ptr to store trie node children

A trie is also a tree, which means there are no cycles in the graph. Therefore there is no need to use a std::shared_ptr. Instead, ideally we would just write:

std::unordered_map<char, Node> children;

The map will be the owner of the Nodes, and it will automatically call the destructor of a Node when it is removed from the map.

Unfortunately, this fails to compile with many compilers due to std::unordered_map not being able to handle incomplete types, although Clang 14 and GCC 12 seem to be fine with this.

We can go back to using a smart pointer, but instead of doing it for every Node inside the map, consider that we can just store the whole map in a smart pointer. This saves a lot of memory per child, and as a bonus it also saves about 48 bytes for a Node that doesn't have any children. We don't need std::shared_ptr here, we can use std::unique_ptr:

using child_map = std::unordered_map<char, Node>;
std::unique_ptr<child_map> children;

Then the accessor functions could then look like:

Node* getChild(char c) {
    if (!children)
        return nullptr;

    auto it = children->find(c);
    return (it != children->end()) ? &it->second : nullptr;
}

Node* addChild(char c) {
    if (!children)
        children = std::make_unique<child_map>;

    return &children[c];
}

Another option might be to not use a std::unordered_map at all, but instead have an array of 26 pointers to children, if you are only going to accept words with the lower case, English alphabet:

std::array<std::unique_ptr<Node>, 26> children;

It uses more memory up-front, but it avoids the need to hash keys, and around 10 children it probably uses less memory. If you really want to know what is faster, consider benchmarking the various solutions.

Don't use a std::vector<int> to store coordinates

A std::vector is a very inefficient datastructure if you just need to store a small, fixed number of elements. There are several options you can use to store row and column coordinate pairs:

• using std::array<int, 2>
• using std::pair<int, int>, or even better: struct position { int row; int col; };
• using a single integer of the form row + col * width

In this case, since you often need access to the row and column separately, I would go for the struct position. Then search() becomes like so:

void search(const std::vector<std::vector<char>>& board, 
            const position &loc, 
            std::vector<position> &stack,
            Trie::Node *trieNode) {
    if (trieNode->endFlag) {
        ...
    }

    if (loc.row < 0 || loc.row >= height) return;
    if (loc.col < 0 || loc.col >= width) return;
    if (find(stack.begin(), stack.end(), loc) != stack.end())
        return;
    ...
}