C++ neat solution


  • 0
    H

    This is my solution, if there is a better way or improvement in this solution, please let me know. Thanks.

    class Solution {
    public:
        pair<float,string> helper(vector<int>& nums,int begin,int end,bool sign){
            pair<float,string> res=make_pair(INT_MIN,"");
            if(begin==end)
                return make_pair(float(nums[begin]),to_string(nums[begin]));
            int op=sign?1:-1;
            for(int i=begin+1;i<=end;i++){
                pair<float,string> pleft=helper(nums,begin,i-1,sign);
                pair<float,string> pright=helper(nums,i,end,!sign);
                float temp=pleft.first/pright.first;
                if(res.second=="" || res.first*op<=temp*op){
                    res.first=temp;
                    if(end-i>=1)
                        res.second=pleft.second+"/("+pright.second+")";
                    else
                        res.second=pleft.second+"/"+pright.second;
                }
            }
            
            return res;
        }
        string optimalDivision(vector<int>& nums) {
            int size=nums.size();
            if(size==0) return "";
            return helper(nums,0,size-1,true).second;
        }
    };
    

Log in to reply
 

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