Share my 4ms DP in C++


  • 0
    F

    I've got a hint below this piece of code, about how I come up with the idea of this code. Also, I wrote a parsing function, to parse the string first. But this takes only linear time and shouldn't raise the complexity of the algorithm.

    enter code here
    vector<int> diffWaysToCompute(string input)
    {
        vector<int>numbers;
        string operations;
        parse(input, numbers, operations);      //Parse the input string, get the numbers and operations
    
        const int len = numbers.size();
        vector< vector< vector<int> > >sol(len, vector< vector<int> >(len));
        int row;
        int diff;
    
        for(diff = 0; diff < len; diff++)
        {
            for(row = 0; row < len-diff; row++)
            {
                int col = row+diff;
                if(row == col)
                {
                    sol[ row ][ col ].push_back(numbers[ row ]);
                }
                else
                {
                    int k;
                    for(k = row; k < col; k++)
                    {
                        const vector<int>& list1 = sol[ row ][ k ];
                        const vector<int>& list2 = sol[ k+1 ][ col ];
                        int i,j;
                        for(i = 0; i < list1.size(); i++)
                        {
                            for(j = 0; j < list2.size(); j++)
                            {
                                switch(operations[ k ])
                                {
                                    case '+':
                                        sol[ row ][ col ].push_back(list1[ i ] + list2[ j ]);
                                        break;
                                    case '-':
                                        sol[ row ][ col ].push_back(list1[ i ] - list2[ j ]);
                                        break;
                                    case '*':
                                        sol[ row ][ col ].push_back(list1[ i ] * list2[ j ]);
                                        break;
                                }
                            }
                        }
                    }
                }
            }
        }
    
        return sol[ 0 ][ len-1 ];
    }
    
    void parse(const string& input, vector<int>& numbers, string& operations)
    {
        int count;
        string strNum;
    
        operations.clear();
        numbers.clear();
        strNum.clear();
        for(count = 0; count < input.length(); count++)
        {
            if(input[ count ]=='+' || input[ count ]=='-' || input[ count ]=='*')
            {
                operations += input[ count ];
                numbers.push_back(atoi(strNum.c_str()));
                strNum.clear();
            }
            else
            {
                strNum += input[ count ];
            }
        }
        numbers.push_back(atoi(strNum.c_str()));
    }
    

    If you don't understand this code, here is the hint: think about the matrix chain multiplication problem. The same idea applies here.


Log in to reply
 

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