C++ Solution with Memoization


  • 0
    G
    class Solution {
    public:
    
        vector<vector<vector<int> > > Memo;
    
        vector<int> DiffWaysToCompute(const string &input,int s, int e)
        {
            vector<int> Result;
            
            for(int i = s; i < e; ++i)
            {
                if(isdigit(input[i]) == false)
                {
                    
                    vector<int> Left; //= DiffWaysToCompute(input,s,i);
                    vector<int> Right; //= DiffWaysToCompute(input,i + 1,e);
                    
                    if(Memo[s][i].empty())
                    {
                        Left = DiffWaysToCompute(input,s,i);
                        Memo[s][i] = Left;
                    }
                    else
                    {
                        Left = Memo[s][i];
                    }
                    
                    if(Memo[i + 1][e].empty())
                    {
                        Right = DiffWaysToCompute(input,i + 1,e);
                        Memo[i + 1][e] = Right;
                    }
                    else
                    {
                        Right= Memo[i + 1][e];
                    }
                    
                    for(auto &l : Left)
                    {
                        for(auto &r : Right)
                        {
                            if(input[i] == '+')
                            {
                                Result.push_back(l + r);
                            }
                            else if(input[i] == '-')
                            {
                                Result.push_back(l - r);
                            }
                            else
                            {
                                Result.push_back(l * r);
                            }
                        }
                    }
                }
            }
            
            if(Result.empty())
            {
                istringstream ss(input.substr(s,e - s));
                int Num = 0;
                ss >> Num;
                Result.push_back(Num);
            }
            
            Memo[s][e] = Result;
            
            return (Result);
        }
    
        vector<int> diffWaysToCompute(string input) 
        {
            
            Memo.resize(input.size());
            
            for(int i = 0; i < input.size(); ++i)
            {
                Memo[i].resize(input.size() + 1);
            }
            
            return DiffWaysToCompute(input,0,input.size());    
        }
    };

Log in to reply
 

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