Can someboday tell me why I was wrong(show me a simple),the wrong case is very large. My code is not complex.Thanks


  • 0
    C

    int minCut(string s)
    {

    if(s.empty()==true || s.length()==1)
        return 0;
    vector<int> DPCut(s.length(),0);
    int num=0;  
    DPCut[0]=0;
    if(s[0]==s[1])
        DPCut[1]=0;
    else
        DPCut[1]=1;
    if(s.length()==2)
        return *(DPCut.end()-1);
    for(int i=2;i<s.length();i++) 
    {
        if(num==0)
            num=i;
        int DPa=s.length();
        int DPb=s.length();
        int DPc=s.length();
        int numa=s.length();
        int numb=s.length();
        int numc=s.length();
        if(s[i]!=s[i-1] && s[i]!=s[i-2] && s[i]!=s[num-1])
        {
            num=i;
            DPCut[i]=DPCut[i-1]+1;
            continue;
        }
        if(s[i]==s[i-1])
        {
            DPa=min(DPCut[i-1]+1,DPCut[i-2]+1);
            numa=i-1;
        }
        if(s[i]==s[i-2])
        {
            if(i>=3)
                DPb=min(DPCut[i-1]+1,DPCut[i-3]+1);
            else
                DPb=0;
            numb=i-2;
        }
        if(s[i]==s[num-1])
        {
            if(num>=2)
            {
                DPc=min(DPCut[i-1]+1,DPCut[num-2]+1);
                numc=num-1;
            }
            else
            {
                DPc=0;
                numc=0;
            }
        }
        DPCut[i]=min(min(DPa,DPb),DPc);
        num=min(min(numa,numb),numc);
    }
    return  *(DPCut.end()-1);
    

    }


Log in to reply
 

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