Solution to Shortest Palindrome by LeetCode

Question: https://leetcode.com/problems/shortest-palindrome/

Question Name: Shortest Palindrome

This is a variant of Longest Palindromic Substring. The key point is to convert the original question as following:
1. Shortest Palindrome by adding any characters in the head. Therefore the original string “original” is going to be “***original”. Because the inserted characters could be ANY thing, we can guarantee that the added sub-string is a mirror of the tailing sub-string. So the question turns out to be:
2. Convert the original string to a palindrome by removing characters at the end of it. Furthermore, it’s equal to:
3. In the original string, what’s the longest Palindrome sub-string, which starts at the index 0.

class Solution(object):

def shortestPalindrome(self, s):

"""

:type s: str

:rtype: str

"""

newS = "#"+"#".join(s)+"#"

palHalfLenCenteringHere = [1] * len(newS)

center, right = 0,1

for index in xrange(1, len(newS)):

if index < right and index + palHalfLenCenteringHere[2*center-index] < right:

# No way to extend the right. Thus the center is not changed.

palHalfLenCenteringHere[index] = palHalfLenCenteringHere[2*center-index]

else:

# We MIGHT extend the right. And we DO change the center here.

# IF we did NOT extend the right, the new center and old one have completely

# the SAME effect on the next steps/rounds.

center = index

if index < right:

# Use some pre-computed information

palHalfLenCenteringHere[index] = right - center

else:

# Actually scanning from scratch

palHalfLenCenteringHere[index] = 1

right += 1

# Try to extend the right

while right < len(newS) and 2*center-right >= 0 and \

newS[right] == newS[2*center-right]:

right += 1

palHalfLenCenteringHere[index] += 1

# Find the longest palindromic substring, which starts at the beginning.

# We travel from the middle point to the begin point. Therefore the first

# qualified sub-string is the longest one.

for center in xrange(len(newS)//2, -1, -1):

# Check whether this palindromic substring starts at index 0.

if center - palHalfLenCenteringHere[center] + 1 == 0:

halfLen = palHalfLenCenteringHere[center]

result = newS[center + halfLen:][::-1] + newS

return result.replace("#", "")

# Should never be here.

return None

Just let you know that I have a pretty messy AC as well. A more elegant solution I peeked from discussion section is: reverse first and then compare substring, which requires an extra O(N) space and O(N^2) time complexity due to substring comparison. And fancier ones use KMP…
My version has no algorithm applied at all, simply “brute force” to cover all edge cases. Stupid but not simple ^_^, no extra space and pretty fast though…

#include <limits>

#include <string>

#include <sstream>

using namespace std;

class SolutionShortestPalindrome {

public:

//Works, but not elegant

string shortestPalindrome1(string s) {

int len = s.length();

ostringstream os;

int loob = numeric_limits<int>::min(), uoob = numeric_limits<int>::max();

int begin = 0, end = len, endsofar = len, prevchar = loob, lasthead = 0;

while (begin < endsofar)

{

if (prevchar != loob && prevchar != uoob && s[end] == prevchar)

end += begin - 1;

else if (end - begin == 1 && lasthead > 0 && lasthead < endsofar)

end = lasthead;

else

--end;

endsofar = end;

begin = lasthead = 0;

prevchar = loob;

while (begin < end && s[begin] == s[end])

{

if (loob == prevchar)prevchar = s[end];

else if (prevchar != s[end])prevchar = uoob;

if (s[0] == s[end])lasthead = end;

begin++, --end;

}

if (s[end] == s[0])lasthead = end;

if (begin >= end)

{

for (int i = len - 1; i > endsofar; --i)

os << s[i];

break;

}

return os.str() + s;

}

};

Solution to Shortest Palindrome by LeetCode

2 Replies to “Solution to Shortest Palindrome by LeetCode”

Leave a Reply Cancel reply