[C++] Three different clean solutions


  • 0
    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            return method3(input); // or method2(input), or method1(input)
        }
    private:
        //------------------------------------------------------------
        // Method1: Brute-force (Recursive)
        vector<int> method1(string &input) {
            int n = input.size();
            return helper1(0, n-1, input);
        }
        vector<int> helper1(int start, int end, string &input) {
            if (start > end) return {};
            vector<int> results;
            for (int i = start; i <= end; i++)
                if (input[i] == '+' || input[i] == '-' || input[i] == '*')
                    for (int a : helper1(start, i - 1, input))
                        for (int b : helper1(i + 1, end, input))
                            input[i] == '+' ? results.push_back(a + b) :
                            input[i] == '-' ? results.push_back(a - b) : results.push_back(a * b);
            if (results.empty()) 
                results.push_back(stoi(input.substr(start, end - start + 1)));
            return results;
        }
        
        //------------------------------------------------------------
        // Method2: Dynamic Programming (Top-down, Recursive + Memoization)
        vector<int> method2(string &input) {
            int n = input.size();
            vector<vector<vector<int>>> mem (n, vector<vector<int>>(n));
            return helper2(0, n-1, input, mem);
        }
        vector<int> helper2(int start, int end, string &input, vector<vector<vector<int>>> &mem) {
            if (!mem[start][end].empty()) 
                return mem[start][end];
            for (int i = start; i <= end; i++)
                if (input[i] == '+' || input[i] == '-' || input[i] == '*')
                    for (int a : helper2(start, i - 1, input, mem))
                        for (int b : helper2(i + 1, end, input, mem))
                            input[i] == '+' ? mem[start][end].push_back(a + b) :
                            input[i] == '-' ? mem[start][end].push_back(a - b) : mem[start][end].push_back(a * b);
            if (start <= end && mem[start][end].empty())
                mem[start][end].push_back(stoi(input.substr(start, end - start + 1)));
            return mem[start][end];
        }
        
        //------------------------------------------------------------
        // Method3: Dynamic Programming (Bottom-up, Iterative)
        vector<int> method3(string &input) {
            std::istringstream iss (input + '.'); // adding a dummy operator
            vector<int> operands;
            vector<char> operators;
            int num;
            char op;
            while (iss >> num && iss >> op) {
                operands.push_back(num);
                operators.push_back(op);
            }
            operators.pop_back(); // removing the dummy operator
            int n = operands.size();
            vector<vector<vector<int>>> dp (n, vector<vector<int>>(n));
            for (int i = 0; i < n; i++) 
                dp[i][i].push_back(operands[i]);
    
            for (int l = 1; l < n; l++)
                for (int i = 0; i < n - l; i++) {
                    int j = i + l;
                    for (int k = i; k < j; k++)
                        for (int a : dp[i][k])
                            for (int b : dp[k+1][j])
                                operators[k] == '+' ? dp[i][j].push_back(a + b) :
                                operators[k] == '-' ? dp[i][j].push_back(a - b) : dp[i][j].push_back(a * b);
                }
            return dp[0][n-1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.