dp c++ 4ms accepted


  • 0
    K

    int fn(string s);
    vector<int> ans;
    map<string,vector<int> > mp_m;
    int fn(string s,vector<int> &e)
    {
    int cnt=0;
    cnt+=count(s.begin(),s.end(),'-');
    cnt+=count(s.begin(),s.end(),'+');
    cnt+=count(s.begin(),s.end(),'');
    if(cnt==0)
    {
    istringstream buffer(s);
    int value;
    buffer >> value;
    e.push_back(value);
    return value;
    }
    for(int i=1;i<=cnt;i++)
    {
    vector<int> qv,qe;
    int mn=0;
    string gf="";
    int m=0;
    while(mn!=i)
    {
    if(s[m]=='+'||s[m]=='-'||s[m]=='
    ')
    mn++;

                if(mn==i)
                    break;
                else
                {
                     string tmp(1,s[m]);
                      gf=gf.append(tmp);
                }
                m++;
           }
           if(mp_m.find(gf)!=mp_m.end())
           {
              qv=mp_m[gf];
           }
           else
           {
              fn(gf,qv);
              mp_m[gf]=qv;
            }
    
            if(mp_m.find(s.substr(m+1))!=mp_m.end())
            {
                qe=mp_m[s.substr(m+1)];
            }
            else
            {
                fn(s.substr(m+1),qe);
                mp_m[s.substr(m+1)]=qe;
            }
           for(int z=0;z<qv.size();z++)
           {
               for(int y=0;y<qe.size();y++)
               {
                    if(s[m]=='+')
                        e.push_back(qv[z]+qe[y]);
                    else if(s[m]=='-')
                        e.push_back(qv[z]-qe[y]);
                       else if(s[m]=='*')
                        e.push_back(qv[z]*qe[y]);
               }
           }
       }
       return 0;
    }
    void fw(string s,vector<int> &e)
    {
        
        int cnt=0;
       cnt+=count(s.begin(),s.end(),'-');
       cnt+=count(s.begin(),s.end(),'+');
       cnt+=count(s.begin(),s.end(),'*');
       if(cnt==0)
       {
            istringstream buffer(s);
            int value;
            buffer >> value; 
            e.push_back(value);
            return;
       }
       for(int i=1;i<=cnt;i++)
       {
           vector<int> qv,qe;
           int mn=0;
           string gf="";
           int m=0;
           while(mn!=i)
           {
               if(s[m]=='+'||s[m]=='-'||s[m]=='*')
                    mn++;
          
                if(mn==i)
                    break;
                else
                {
                     string tmp(1,s[m]);
                      gf=gf.append(tmp);
                }
                m++;
           }
           if(mp_m.find(gf)!=mp_m.end())
           {
              qv=mp_m[gf];
           }
           else
           {
              fn(gf,qv);
              mp_m[gf]=qv;
            }
    
            if(mp_m.find(s.substr(m+1))!=mp_m.end())
            {
                qe=mp_m[s.substr(m+1)];
            }
            else
            {
                fn(s.substr(m+1),qe);
                mp_m[s.substr(m+1)]=qe;
            }
           for(int z=0;z<qv.size();z++)
           {
               for(int y=0;y<qe.size();y++)
               {
                    if(s[m]=='+')
                        e.push_back(qv[z]+qe[y]);
                    else if(s[m]=='-')
                        e.push_back(qv[z]-qe[y]);
                       else if(s[m]=='*')
                        e.push_back(qv[z]*qe[y]);
               }
           }
    
    
       }
    }
    vector<int> diffWaysToCompute(string s) {
        
        vector<int> df;
        if(s.size()==0)
            return df;
       fw(s,df);
       sort(df.begin(),df.end());
       cout<<df[df.size()-1]<<" "<<df[0]<<endl;
       return df;
    }

  • 0

    @kishan7 Your code is really formatted in a mess. Could you just format it properly using three backquotes ```? Thank you so much!


Log in to reply
 

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