7
\$\begingroup\$

The task is taken from LeetCode. I would appreciate an assessment of whether my coding style follows good practices. I'm fairly familiar with algorithms and data structures so I'm not really looking for feedback on that end (I could probably have an early exit if nbParenthesesToClose > maxIdx - idx and I think the copy constructor of std::string is called too many a time (I show what I think that should look like at the end of the post)).

The thing I'm worried about is that I have seldomly worked with other people so I'm sometimes afraid I picked up some bad habits. Here for example, I feel like my dfs function has "too many arguments". I thought about making a lambda function that captures validParentheses for example so that I don't have to pass it around when I call the recursive dfs calls but that would make the main function bigger and having helper functions is usually considered good. Same goes for maxIdx which doesn't technically need to be passed around. So I'm a bit confused as to what I should do.

Problem statement

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example:

Input:

n = 3

Output:

["((()))","(()())","(())()","()(())","()()()"]

My solution (C++):

void dfs(
        const int idx,
        const int maxIdx,
        const int nbParenthesesToClose,
        const std::string& currString,
        std::vector<std::string>& validParentheses
    )
{
    // Sanity Check
    assert(nbParenthesesToClose >= 0);
        
    // Base Case
    if (idx == maxIdx)
    {
        if (nbParenthesesToClose == 0)
        {
            validParentheses.push_back(currString);
        }
        return;
    }
    
    // Recursive calls
    dfs(idx + 1, maxIdx, nbParenthesesToClose+1, currString + "(", validParentheses);
    if (nbParenthesesToClose > 0)
    {
        dfs(idx + 1, maxIdx, nbParenthesesToClose-1, currString + ")", validParentheses);
    }
}

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        // validParentheses will contain the valid strings
        std::vector<std::string> validParentheses;

        dfs(0, 2*n, 0, "", validParentheses);

        return validParentheses;
    }
};

If anyone wants to look at what I think the "optimised" version of the code from a algorithm point of view would be:

std::string stackToString(std::stack<char> s)
{
    // pass by copy because we'll "consume" the whole stack when doing the conversion
    std::string result;
    result.reserve(s.size());

    while (!s.empty()) {
        result.push_back(s.top());
        s.pop();
    }

    std::reverse(result.begin(), result.end());
    return result;
}

void dfs(
        const int idx,
        const int maxIdx,
        const int nbParenthesesToClose,
        std::stack<char>& currString,
        std::vector<std::string>& validParentheses
    )
{
    // Sanity Check
    assert(nbParenthesesToClose >= 0);
        
    if (idx == maxIdx)
    {
        if (nbParenthesesToClose == 0)
        {
            validParentheses.push_back(stackToString(currString));
        }
        return;
    }
    
    currString.push('(');
    dfs(idx + 1, maxIdx, nbParenthesesToClose+1, currString, validParentheses);
    currString.pop();
    if (nbParenthesesToClose > 0)
    {
        currString.push(')');
        dfs(idx + 1, maxIdx, nbParenthesesToClose-1, currString, validParentheses);
        currString.pop();
    }
}

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        // validParentheses will contain the valid strings
        std::vector<std::string> validParentheses;
        std::stack<char> currString;

        dfs(0, 2*n, 0, currString, validParentheses);

        return validParentheses;
    }
};
\$\endgroup\$

2 Answers 2

Reset to default
6
\$\begingroup\$

By default, std::stack uses std::deque as its underlying container. However, this is just the default, and any container which implements SequenceContainer as well as push_back, pop_back, and back can be provided as that underlying container.

The std::string class provides these requirements, and storing your stack as a std::string will greatly reduce the work done as you convert to a string, since there's no need to actually do any computation: you already have the underlying string.

But std::stack keeps its underlying container as a protected member which we can't access (since that would let us break the LIFO contract). So we inherit from std::stack and implement access to that container c as a member function.

#include <string>
#include <stack>

struct CharStack : std::stack<char, std::string> {
    std::string to_string() {
        return c;
    }
};
\$\endgroup\$
4
  • 2
    \$\begingroup\$ That's a clever usage of stack. \$\endgroup\$ Commented 15 hours ago
  • 2
    \$\begingroup\$ Seems to me like it'd be easier to just use an std::string directly, and replace push with push_back and pop with pop_back. \$\endgroup\$ Commented 5 hours ago
  • \$\begingroup\$ That's basically what std::stack<char, std::string> is doing. \$\endgroup\$ Commented 5 hours ago
  • \$\begingroup\$ @Chris: yes, but in a much more roundabout way. \$\endgroup\$ Commented 4 hours ago
3
\$\begingroup\$

This is a review of the first code block. I might also review the second one later.

Missing includes - I needed to include <cassert>, <string> and <vector> before I could even compile the code.

This test suggests we perhaps ought to be using an unsigned type for the variable:

assert(nbParenthesesToClose >= 0);

I would suggest that idx and maxIdx also should be unsigned - probably std::size_t to match std::string::size().

We unconditionally recurse with ( even when we won't be able to close all the ones that we open. We can avoid all those fruitless branches by being more selective:

    if (nbParenthesesToClose < maxIdx - idx) {
        dfs(idx + 1, maxIdx, nbParenthesesToClose+1, currString + '(', validParentheses);
    }

This also allows us to eliminate the test within the idx == maxIdx block, since nbParenthesesToClose now always becomes 0 when we reach the end.

We're passing both idx and maxIdx through every call, but don't really need both. We just care how many characters remain to be added, which is maxIdx - idx, so we could pass that count instead. Here's what that looks like (with some light renaming to give shorter parameters):

#include <cstddef>
#include <string>
#include <utility>
#include <vector>

void dfs(const std::size_t nchars,
         const std::size_t open_parens,
         std::string candidate,
         std::vector<std::string>& result)
{
    // Base Case
    if (nchars == 0) {
        result.push_back(std::move(candidate));
        return;
    }

    // Recursive calls
    if (open_parens < nchars) {
        dfs(nchars - 1, open_parens + 1, candidate + '(', result);
    }
    if (open_parens > 0) {
        dfs(nchars - 1, open_parens - 1, candidate += ')', result);
    }
}
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.