What's wrong with this?


  • 0
    C

    The following is my code.
    A static vector 'minCutRemain' to record the minCut of the remaining list.
    And the update of the vector is mainly by

            if( isPalindrome(s.substr(inx,start-inx))){
                if( minCutRemain[start]==-1 ){
                    minCutRemain[start]=minCutSub(s,start);
                }
                maxL = min(maxL, minCutRemain[start]+1);
            }
    

    but the result is reported wrong with '1eet'(which is 1 while the right answer is 2), however when tested with visual studio, the answer is 2. I cannot figure out why, can anyone kindly help?

    class Solution {
    public:
        bool isPalindrome(string s){
            int start=0, end = s.length()-1;
            while(start<end){
                if(s[start]!=s[end])
                    return false;
                start++;
                end--;
            }
            return true;
        }
        int minCutSub(string &s, int inx){
            
            int L = s.length();
            static vector<int> minCutRemain(L,-1);
            if( isPalindrome(s.substr(inx,L-inx)) ){
                minCutRemain[inx] = 0;
                return minCutRemain[inx];
            }
            int maxL = L;
            for( int start = inx+1; start<L; start++ ){
                if( isPalindrome(s.substr(inx,start-inx))){
                    if( minCutRemain[start]==-1 ){
                        minCutRemain[start]=minCutSub(s,start);
                    }
                    maxL = min(maxL, minCutRemain[start]+1);
                }
            }
            minCutRemain[inx] = maxL;
            return maxL;
            
        }
        int minCut(string s) {
            return minCutSub(s,0);
            
        }
    };

Log in to reply
 

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