0ms 2D dynamic programming code O(n^2) (C++)


  • 1
    C
    class Solution {
    private:
        vector<int> nums;
        vector<char> ops;
        vector<vector<vector<int> > > rec;
        int len;
    public:
        vector<int> diffWaysToCompute(string input) {
            if(input.empty())
                return vector<int>();
            store_info(input);
    
            if(ops.empty())
                return nums;
            len = nums.size();
            rec = vector<vector<vector<int> > >(len, vector<vector<int>>());
            for(int i = 0; i<len; ++i)
                rec[i] = vector<vector<int> >(len, vector<int>());
            calc_all();
            return rec[0][len-1];
        }
        
        void store_info(string input)
        {
            int cur = 0;
            int pre = 0;
            for(; cur<input.size(); ++cur)
            {
                if(input[cur] == '-' || input[cur] == '*' || input[cur] == '+')
                {
                    nums.push_back(stoi(input.substr(pre, cur-pre)));
                    ops.push_back(input[cur]);
                    pre = cur+1;
                }
            }
            nums.push_back(stoi(input.substr(pre, cur-pre)));
        }
        
        
        void calc_all()
        {
            for(int dist = 0; dist<len; ++dist)
            {
                for(int i = 0; i<len-dist; ++i)
                {
                    if(dist == 0)
                        rec[i][i+dist].push_back(nums[i]);
                    else
                    {
                        for(int j = 0; j<dist; ++j)
                            merge_res(rec[i][i+j], rec[i+j+1][i+dist], ops[i+j], i, dist);
                    }
                }
            }
        }
        
        void merge_res(vector<int>& res_l, vector<int>& res_r, char op, int pos, int dist)
        {
            for(int i = 0; i<res_l.size(); ++i)
                for(int j = 0; j<res_r.size(); ++j)
                    rec[pos][pos+dist].push_back(calculate(res_l[i], res_r[j], op));
        }
        
        int calculate(int num1, int num2, char op)
        {
            if(op == '+')
                return num1+num2;
            else if(op == '-')
                return num1-num2;
            else if(op == '*')
                return num1*num2;
        }
        
    
    };

  • 0
    S

    I think it's not O(n^2) time complexity. The size of return vector Catalan number (bigger than 3^n). You have three dimention vector<vector<vector<int> > > rec; so you must fill it. It's more than n^3 time.


Log in to reply
 

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