Solutions in C++, check it and you will get it.


  • 2

    Solution

    Analysis

    Adding parentheses here is actually changing the calculation order and intuitively we can come up with a solution using recursion which via a calculation string and output the different results for different parentheses. Recursion can be solved by itself in limited range, which is the core of it.

    • to avoid further modifying the input string, we use begin and end to limit the range and in each invoking we create a new vector to store the results, then we return the vector;
    • the last calculation which can happen in all the operators, so we split the string by the different operators (sometimes we have to think in a reverse opposite way to ease the difficulty, so here we care about the last) so as the recursion rule goes, the left and right substring will also have different results themselves and now what we need to do is combine them with the last operator one by one;
    • as for termination condition: there is no operator between begin and end position, so we then can just convert the string to an integer and return.

    Pure recursive

    The recursive solution in C++ is as follows:

    class Solution {
    private:
        int sLen;
        vector<int> helper(const string& s, int begin, int end)
        {
            vector<int> v;
            if(begin > end) return v; 
            for(int i = begin; i <= end; ++i)
            {
                if(!isdigit(s[i]))
                {
                    vector<int> l = helper(s, begin, i-1), r = helper(s, i+1, end);
                    for(int j = 0; j < l.size(); ++j)
                    {
                        for(int k = 0; k < r.size(); ++k)
                        {
                            switch(s[i])
                            {
                                case '-': v.push_back(l[j]-r[k]); break;
                                case '+': v.push_back(l[j]+r[k]); break;
                                case '*': v.push_back(l[j]*r[k]); break;
                            }
                        }
                    }
                }
            }
            if(v.empty()) v.push_back(stoi(s.substr(begin, end-begin+1)));
            return v;
        }
    public:
        vector<int> diffWaysToCompute(string input) {
            sLen = input.length();
            return helper(input, 0, sLen-1);
        }
    };
    

    There is a more terse solution in C++, though less efficient.

    vector<int> diffWaysToCompute(string s) 
    {
    	if(s.empty()) return vector<int>();
    	vector<int> v;
    	for(int i = 0; s[i]; ++i)
    	{
    		if(!isdigit(s[i]))
    		{
    			for(int a: diffWaysToCompute(s.substr(0, i)))
    				for(int b: diffWaysToCompute(s.substr(i+1)))
    				{
    					if(s[i] == '-') v.push_back(a-b);
    					if(s[i] == '+') v.push_back(a+b);
    					if(s[i] == '*') v.push_back(a*b);
    				}
    		}
    	}
    	return v.size()? v : vector<int>{stoi(s)};
    }
    

    Memoization

    Of course, there should be a DP or Memoization solution, since there are lots of overlapping sub-problems and when the string becomes large, its performance will be definitely a problem. So here is a Memoization solution in C++. DP can do also do but that will be wanting in simplicity here. But so notoriuos as Momoization always is, the space it's to cost is rather costly here. Balance it in different cases is what we should always care about.

    class Solution {
    private:
        int sLen;
        vector<int> helper(const string& s, int begin, int end, vector<vector<vector<int>>>& matrix)
        {
            vector<int> v;
            if(begin > end) return v; 
            if(matrix[begin][end].size()) return matrix[begin][end];
            for(int i = begin; i <= end; ++i)
            {
                if(!isdigit(s[i]))
                {
                    vector<int> l = helper(s, begin, i-1, matrix), r = helper(s, i+1, end, matrix);
                    for(int j = 0; j < l.size(); ++j)
                    {
                        for(int k = 0; k < r.size(); ++k)
                        {
                            switch(s[i])
                            {
                                case '-': v.push_back(l[j]-r[k]); break;
                                case '+': v.push_back(l[j]+r[k]); break;
                                case '*': v.push_back(l[j]*r[k]); break;
                            }
                        }
                    }
                }
            }
            matrix[begin][end] = v.size()? v : vector<int>{stoi(s.substr(begin, end-begin+1))};
            return matrix[begin][end];
        }
    public:
        vector<int> diffWaysToCompute(string input) {
            sLen = input.length();
            vector<vector<vector<int>>> matrix(sLen, vector<vector<int>>(sLen));
            return helper(input, 0, sLen-1, matrix);
        }
    };
    

    DP

    It's not good to leave the DP alone. So here it is, the DP solution though it's not that intuitive and easy to accomplish as Memoization.

    • split the input string into number strings and operator strings
    • start to calculate from one string till all of them including numbers and operators
    • move 2 steps forward each time since there are operators among numbers, while we only care about numbers
    • in each range, we only calculate when encountering operators and as before we combine the results from left side and right side using the current operator

    The whole solution in C++ is as follows. In summary, though it's not that intuitive to achieve a DP solution here, but it's quite a balance between performance and space cost between recursive (which re-calculates lots of over-lapping sub-problems) and Memoizationet (which costs lots of redundant space not only in storing but recursive function invoking).

    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) 
        {
            vector<string> parts;
            string s;
            for(int i = 0; i <= input.length(); ++i)
            {
                if(isdigit(input[i])) s += input[i];
                else
                {
                    parts.push_back(s);
                    s.clear();
                    if(input[i] != '\0') parts.push_back(string(1, input[i]));
                }
            }
            int size = parts.size();
            vector<vector<vector<int>>> matrix(size, vector<vector<int>>(size));
            for(int d = 0; d < size; d += 2)
            {
                for(int l = 0; l < size-d; ++l)
                {
                    if(!isdigit(parts[l][0])) continue;
                    if(d == 0) matrix[l][l].push_back(stoi(parts[l]));
                    int r = l+d;
                    for(int k = l; k <= r; ++k)
                    {
                        if(!isdigit(parts[k][0]))
                        {
                            for(auto a: matrix[l][k-1])
                                for(auto b: matrix[k+1][r])
                                {
                                    if(parts[k] == "-") matrix[l][r].push_back(a-b);
                                    if(parts[k] == "+") matrix[l][r].push_back(a+b);
                                    if(parts[k] == "*") matrix[l][r].push_back(a*b);
                                }
                        }
                    }
                }
            }
            return matrix[0][size-1];
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    S

    @LHearen Awesome as usual, almost all types of solutions are provided!


  • 1
    S

    @LHearen I further optimized your DP solution, very awesome.

    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            string s;
            vector<string> parts;
            for(int i = 0; input[i]; ++i){
                if(isdigit(input[i])) s += input[i];
                else{
                    parts.push_back(s);
                    s = input[i];
                        parts.push_back(s);
                    s.clear();
                }
            }
            parts.push_back(s); //collect the last number;
            int size = parts.size();
            vector<vector<vector<int>>> matrix(size, vector<vector<int>>(size));
            for(int d = 0; d < size; d += 2){
                for(int l = 0; l < size-d; ++l){
                    if(!isdigit(parts[l][0])) continue;
                    int r = l+d;
                    if(!d) matrix[l][l].push_back(stoi(parts[l]));
                    for(int k = l+1; k < r; ++k){
                        if(!isdigit(parts[k][0])){
                            for(auto a: matrix[l][k-1]){
                                for(auto b: matrix[k+1][r]){
                                    switch(parts[k][0]){
                                        case '-': matrix[l][r].push_back(a-b); break;
                                        case '+': matrix[l][r].push_back(a+b); break;
                                        case '*': matrix[l][r].push_back(a*b); break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return matrix[0][size-1];
        }
    };
    

Log in to reply
 

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