7 Dec 2011
Given a string S, find the longest palindrome substring.
A palindrome string is a string and its reverse are the same.
my dynamic programming skill is still ok.
First of all, we can immediately see the brute force solution. If you cannot see it right away, you shouldn't be a programmer…
Let's start with how the palindrome can be decomposed. Let's say we have a palindrome:
a a a a a a is a palindrome
We can see that:
a a a a must be a palindrome So does a a
We can construct a palindrome from a shorter one. That gives us the solution:
d[i,j] = true if a[i] ... a[j] is a palindrome d[i,j] is a palindrome iff d[i+1,j-1] is a palindrome and a[i] == a[j] d[i,i] is a palindrome d[i,i+1] is a palindrome iff a[i] == a[i+1]
The solution is O(n2) and O(n2) in space.
I don't know why I didn't see this solution. I was too much into the algorithm techniques like dynamic programming…
We can just iterate all possible centers (of a palindrome). There are 2n-1 possible centers. (ones at a character and ones between 2 characters)
At each center c, we check for the longest one, which takes only O(n). Each loop we check if a[c-i] == a[c+i].
This solution takes only O(n^2) with O(1) in space.
There is also a O(n) solution, but it's a little bit complicated.
This algorithm observes one more property of a palindrome. I should learn that for every property discovered, the algorithm can be optimized.
a a a a a a a a a is a palindrome (a is a center) If a a a is a palindrome, then a a a is also a palindrome. Actually, if any a[i]..a[j] is a palindrome, there is a mirror around a that is also a palindrome. This is because the above string is a a a a a a a a a
With this property, we can disregard some case, which reduces the time complexity to O(n).
I'll leave this as an exercise for future Tanin. :)