Found a shorter answer for a test case


  • 0
    J

    I received Wrong Answer with the following:

    Input:
    "nllynrwlxijbpxtrtwnxxaetdtwzcbljckitulbfurcxlcnlpbp"

    Output:
    "nllynrwlxijbpxtrtwnxxaetdtwzcbljckitulbfurcxlcnlpbplnclxcrufblutikcjlbczwtdteaxxnwtrtxpbjixlwrnylln"

    Expected:
    "pbplnclxcrufblutikcjlbczwtdteaxxnwtrtxpbjixlwrnyllnllynrwlxijbpxtrtwnxxaetdtwzcbljckitulbfurcxlcnlpbp"

    My answer is shorter and I'm pretty sure it's also palindrome.
    I would be delighted if anyone pointed out my mistakes.

    My idea was to find the longest palindrome string that includes the first or the last character from the input, and then simply add the remaining substrings to the other side of this palindrome string.

    This is my code, pretty ugly but it should work:

    class Solution:
        # @param {string} s
        # @return {string}
        
        def __init__(self):
            self.idic={}
            self.jdic={}
            self.idics=0
            self.jdics=0
    
        def isPal(self,s,mode):
            n=len(s)
            for i in range(0,n/2):
                if s[i]==s[n-i-1]:
                    pass
                else:
                    return False
            return True
    
        def addDic(self,mode,ch):
            if mode==0:
                if ch in self.idic:
                    self.idic[ch]+=1
                else:
                    self.idic[ch]=1
                    self.idics+=1
                return self.idics
            else:
                if ch in self.jdic:
                    self.jdic[ch]+=1
                else:
                    self.jdic[ch]=1
                    self.jdics+=1
                return self.jdics
    
        def precheck(self,lastmax,cur,s):
            if lastmax+1>cur-lastmax+1:
                return False
            else:
                return True
        
        def shortestPalindrome(self, s):
            maxi=0
            maxj=0
            n=len(s)
            for i in range(0,n):
                dicsize=self.addDic(0,s[i])
                print self.idic
                if dicsize==1 or (self.precheck(maxi,i,s) and maxi<i+1 and self.isPal(s[:i+1],0)):
                    maxi=i+1
            print maxi
    
            maxj=maxi
            rs=s[::-1]
            for j in range(0,n):
                dicsize=self.addDic(1,rs[j])
                if dicsize==1 or (j>=maxi and self.precheck(maxj,j,rs) and maxj<j+1 and self.isPal(rs[:j+1],1)):
                    maxj=j+1
            print maxj
            
            if maxj>maxi:
                print s[:n-maxj]
                return s+s[:n-maxj][::-1]
            else:
                print s[maxi:]
                return s[maxi:][::-1]+s
    
    a=Solution()
    s="nllynrwlxijbpxtrtwnxxaetdtwzcbljckitulbfurcxlcnlpbp"
    print a.shortestPalindrome(s)

  • 2
    S

    Given a string S, you are allowed to convert it to a palindrome by
    adding characters in front of it.

    "nllynrwlxijbpxtrtwnxxaetdtwzcbljckitulbfurcxlcnlpbp"
    "nllynrwlxijbpxtrtwnxxaetdtwzcbljckitulbfurcxlcnlpbplnclxcrufblutikcjlbczwtdteaxxnwtrtxpbjixlwrnylln"

    in your answer you added characters to the back of the input string, not in front of it


  • 0
    J

    Thanks, what is wrong with my eyes.


Log in to reply
 

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