Leetcode 241 Solution

This article provides solution to leetcode question 241 (different-ways-to-add-parentheses)
Categories:
Tags:
Access this page by simply typing in "lcs 241" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/different-ways-to-add-parentheses

Solution

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> nums;
        vector<char> operators;

        int lastval = 0;

        for (auto ch : input)
        {
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
            {
                nums.push_back(lastval);
                operators.push_back(ch);

                lastval = 0;
            }
            else
                lastval = lastval * 10 + ch - '0';
        }

        nums.push_back(lastval);

        int m = nums.size();
        vector<vector<int>> dp(m * m, vector<int>());

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j + i < m; j++)
            {
                if (i == 0)
                    dp[j * m + j].push_back(nums[j]);
                else
                {
                    for (int k = 0; k < i; k++)
                    {
                        for (auto val1 : dp[j * m + j + k])
                            for (auto val2 : dp[(j + k + 1) * m + j + i])
                            {
                                int val3 = INT_MIN;
                                switch (operators[j + k])
                                {
                                    case '+': val3 = val1 + val2; break;
                                    case '-': val3 = val1 - val2; break;
                                    case '*': val3 = val1 * val2; break;
                                    case '/': val3 = val1 / val2; break;
                                }

                                dp[j * m + j + i].push_back(val3);
                            }
                    }
                }
            }
        }

        return dp[nums.size() - 1];
    }
};