Code giving different answers while testing and while submitting


  • 0
    S

    When I am testing this code for input "ab" it is giving correct answer as 1.
    But when it is submitted to OJ I see output as 1.

    int minCut(string s)
    {
    int n = s.length();
    if(n==0 || n==1)
    {
    return 0;
    }

        bool ** P = new bool*[n];
        for(int i=0;  i<n; ++i)
        {
            P[i] = new bool[n];
        }
        
        for(int i=0; i<n; ++i)
        {
            P[i][i] =true;
            //cout<<P[i][i]<<" ";
            if(i>0 && s[i-1] == s[i])
            {
              P[i-1][i] = true;
            }
        }
        
        for(int  l =3; l<=n; ++l)
        {
            for(int i=0; i+l<=n; ++i)
            {
                int j = i+l-1;
                
                if(s[i] == s[j] && P[i+1][j-1] == true)
                {
                    P[i][j] = true;
                }
                else
                {
                    P[i][j] = false;
                }
                    
            }
        }
        
        
        int * M = new int[n];
        M[0] = 0;
        if(P[0][1])
        {
            M[1]=0;
        }
        else
        {
            M[1] = 1;
        }
        
        for(int i=2; i<n; ++i)
        {
            if(P[0][i])
            {
                M[i] = 0;
            }
            else
            {
                int left =0;
                int right = 0;
                 int min =n;
               for(int j=0; j<i; ++j)
               {
                   if(P[0][j] == true)
                   {
                       left = 0;
                   }
                   else
                   {
                       left = M[j];
                   }
                   if(P[j+1][i] == true)
                   {
                       right = 0;
                   }
                   else
                   {
                       right = M[i-1]+1;
                   }
                   
                   if(min> right+left+1)
                   {
                       min = right + left +1;
                   }
                   
                    //cout<<"i="<<i<<" "<<min<<endl;
               }
               
               M[i] = min;
            }
        }
        int returnVal = M[n-1];
    
       delete[] M;
       return returnVal;
    }
    

    Is something wrong with the code? by the way 25/28 test cases are passed.


Log in to reply
 

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