Weird Wrong Answer.


  • 0
    C

    I got a weird test result like this, have you ever meet the same problem?

    25 / 27 test cases passed. 
    Status: Wrong Answer
    Input:	"apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp" 
    Output:	    453 
    Expected:	452
    

    I used the code in Longest Palindromic Substring as a function.

    This is my code:

    public class Solution {
        public int[] longestPalindrome(String s) {
            if(s==null || s.length()==0) return null;
            int max = 0;
            int pos = 0;
            for(int i=0; i<s.length()*2-1; i+=2)
            {
                int l = 1;
                for(int j=1; j<=i/2 && j<s.length()-i/2; j++)
                {
                    if(s.charAt(i/2-j)==s.charAt(i/2+j)) l+=2;
                    else break;
                }
                if(max<l)
                {
                    max = l;
                    pos = i;
                }
            }
            for(int i=1; i<s.length()*2-1; i+=2)
            {
                int l = 0;
                for(int j=0; j<=i/2 && j<s.length()-i/2-1; j++)
                {
                    if(s.charAt(i/2-j)==s.charAt(i/2+j+1)) l+=2;
                    else break;
                }
                if(max<l)
                {
                    max = l;
                    pos = i;
                }
            }
            return new int[]{pos/2-max/2+(pos%2==0?0:1), pos/2+max/2+1};
        }
        public int minCut(String s) {
            int[] longest = longestPalindrome(s);
            if(longest==null) return 0;
            if(longest[0]==0 && longest[1]==s.length()) return 0;
            if(longest[0]==0) return minCut(s.substring(longest[1]))+1;
            if(longest[1]==s.length()) return minCut(s.substring(0,longest[0]))+1;
            return minCut(s.substring(0,longest[0]))+minCut(s.substring(longest[1]))+2;
        }
    }
    

  • 0
    S

    Would you mind introduce the idea not only code and failed test case? Or it will be closed.


  • 1
    C

    Finally, I found it's indeed a "wrong answer".
    The longest palindromic substring may be not unique, which will lead different result.
    Take string "ababb" as an example, the longest palindromic substring can be "aba" or "bab". The former splits the "ababb" into two palindromic parts, while the latter splits the "ababb" into three palindromic parts.

    I fixed it with the code below.

    public class Solution {
        boolean isPalindrome(String s, int i, int j, boolean[][] palindrome)
        {
            if(i==j) return true;
            if(s.charAt(i)!=s.charAt(j)) return false;
            else if(i+2>=j) return true;
            else return palindrome[i+1][j-1];
        }
        public int minCut(String s) {
            boolean[][] palindrome = new boolean[s.length()][s.length()];
            int[] min = new int[s.length()+1];
            min[0] = -1;
            for(int i=0; i<s.length(); i++)
            {
                min[i+1] = min[i]+1;
                for(int j=i-1; j>=0; j--)
                {
                    if(isPalindrome(s, j, i, palindrome))
                    {
                        if(min[i+1]>min[j]+1) min[i+1] = min[j]+1;
                        palindrome[j][i] = true;
                    }
                }
            }
            return min[s.length()];
        }
    }

  • 0
    C

    Thanks for your suggestion. I found I used a wrong algorithm to solve it.


Log in to reply
 

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