clueless coding // TODO: be smarter

LeetCode 241. Different Ways to Add Parentheses: C++ Solution



Problem Statement


Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Function Signature (C++):
  vector<int> diffWaysToCompute(string input)

Inputs:
  input = "2-1-1"

Outputs:
  [0, 2]

We can add parenthesis in the following ways:
((2-1)-1) -> 0
(2-(1-1)) -> 2



TL;DR Code Solution


vector<int> diffWaysToCompute(string input) {
  
    vector<int> result;

    for (int i = 0; i < input.size(); i++) {

        if (input[i] == '-' || input[i] == '+' || input[i] == '*') {
            vector<int> left = diffWaysToCompute(input.substr(0, i));
            vector<int> right = diffWaysToCompute(input.substr(i + 1));
            for (int itemLeft : left) {
                for (int itemRight : right) {
                    if (input[i] == '-') {
                        result.push_back(itemLeft - itemRight);
                    }
                    if (input[i] == '+') {
                        result.push_back(itemRight + itemLeft);
                    }
                    if (input[i] == '*') {
                        result.push_back(itemRight * itemLeft);
                    }
                }
            }
        }
    }

    if (result.size() == 0) {
        result.push_back(atoi(input.c_str()));
    }

    return result;

}