4ms C++ result with detailed comment


  • 0
    B
    class Solution {
        
        // the operator of operand `i` is operator[i]. The default operator of first operand is '+'
        vector<int> operands;
        vector<char> operators;
        
        void inputParser(string input) {
            // assume input data does not contain any whitespace
            // assume input are always valid, which means there are no "+5--+5" (which should be 5+5) exists
            string tmp_str;
            if (input[0] != '+' && input[0] != '-' && input[0] != '*') {
                operators.push_back('+');
            }
            for(int i = 0; i < input.length(); i++) {
                // find an operator, put into vector
                if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                    operators.push_back(input[i]);
                    if (tmp_str.length() > 0) {
                        operands.push_back(stoi(tmp_str));
                        tmp_str = "";
                    }
                } else {
                    tmp_str += input[i];
                }
            }
            
            if (tmp_str != "") {
                operands.push_back(stoi(tmp_str));
                tmp_str = "";
            }
            
            assert(operands.size() == operators.size());
        }
        
        vector<int> cartesian_product(vector<int> lv, vector<int> rv, char op) {
            vector<int> res;
            for(auto lit = lv.cbegin(); lit != lv.cend(); ++lit) {
                for(auto rit = rv.cbegin(); rit != rv.cend(); ++rit) {
                    switch(op) {
                        case '+' :
                            res.push_back((*lit) + (*rit));
                            break;
                        case '-' :
                            res.push_back((*lit) - (*rit));
                            break;
                        case '*' :
                            res.push_back((*lit) * (*rit));
                            break;
                    }
                }
            }
            return res;
        }
        
    public:
        vector<int> diffWaysToCompute(string input) {
            
            // Parse input
            inputParser(input);
    
            // Construct result matrix
            
            // The result matrix is a 2-by-2 matrix, m[i][j] means the result of a sub-equation 
            // " operand[i] operator[i+1] ... operator[j-1] operand[j]
            // since such sub-equation has multiple possible results, the element in m[i][j] is not a value but a vcector of values.
            
            vector< vector< vector<int> > > m;
            m.resize(operands.size());
            
            // Init matrix and put each operand into m[i][i]
            for(int i = 0; i < operands.size(); i++) {
                m[i].resize(operands.size());
                m[i][i].push_back(operands[i]);
            }
            
            // because m[i][j] depends on m[i+1][j], m[i+2][j], ..., the computation starts at right top corner.
            for(int i = operands.size() - 1; i >= 0; i--) {
                for(int j = i+1; j < operands.size(); j++) {
                    // Compute sub-equation m[i][j]
                    // Try all m[i][z] operator[z+1] m[z+1][j], where z \in [i,j]
                    for(int z = i; z < j; z++) {
                        vector<int> tmp_res = cartesian_product(m[i][z], m[z+1][j], operators[z+1]);
                        m[i][j].reserve(m[i][j].size() + tmp_res.size());
                        m[i][j].insert(m[i][j].end(), tmp_res.begin(), tmp_res.end());
                    }
                }
            }
            
            return(m[0][operands.size() - 1]); // the result of entire equation
            
        }
    };

Log in to reply
 

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