Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
One idea is to test every possible palindrome substring and get the longest one at last. For each index i, the center of palindrome could be s[i] or s[i] and s[i+1]. We can test these two cases and find the longest one. The running time for this one is O(n^2)
Another solution is Manacher's Algorithm, and the description is in the reference link below.
C++ Code:
/*
*func: longest_palindrome_center
*goal: find the longest palindrome based on the input center
*@param s: the input string
*@param center_l: the index of left centroid
*@param center_r: the index of right centroid
*return: the current longest palindrome
*/
string longest_palindrome_center(const string &s, int center_l, int center_r){
assert(center_l >= 0 && center_l < s.length()), assert(center_r < s.length() && center_r >= 0);
assert(center_l <= center_r);
//If the current pair is equal, expand to the next pair
while(center_l >= 0 && center_r < s.length() && s[center_l] == s[center_r]){
--center_l;
++center_r;
}
return s.substr(center_l + 1, center_r - center_l - 1);
}
/*
*func: longest_palindrome
*goal: find the longest palindrome in the input string
*@param s: the input string
*return: the longest palindrome
*/
/*
*basic idea: check the length of every possible palindrome
*complexity: time O(n^2), space O(n)
*/
string longest_palindrome(const string &s){
string result = "";
//Corner Case 1: the string is null
if(s.length() == 0){
return result;
}
//Else the result at least contains 1 letter
result = s.substr(0, 1);
for(int i=0; i<s.size()-1; i++){
//For the case that the palindrome is odd-length
string palindrome_odd = longest_palindrome_center(s, i, i);
//Update the result
if(palindrome_odd.length() > result.length()){
result = palindrome_odd;
}
//For the case that the palindrome is even-length
string palindrome_even = longest_palindrome_center(s, i, i+1);
//Update the result
if(palindrome_even.length() > result.length()){
result = palindrome_even;
}
}
return result;
}
/*
*func: manacher_helper
*goal: insert special character into the string to simplify the problem
*For example: "aba" to "^#a#b#a#$', assume these characters don't exist
*in the string
*@param s: the input string
*return: string after processing
*/
string manacher_helper(const string &s){
//Corner Case
if(s.length() == 0){
return "^$";
}
string result = "^";
for(int i=0; i<s.length(); i++){
result += "#" + s.substr(i,1);
}
result += "#$";
return result;
}
/*
*func: longest_palindrome
*goal: find the longest palindrome in the input string
*@param s: the input string
*return: the longest palindrome
*/
/*
*idea: Manacher's Algorithm
*complexity: time O(n), space O(n)
*/
string longest_palindrome(const string &s){
//string after pre-processing
string curr = manacher_helper(s);
int length = curr.length();
//array for the panlindrome length
int *p = new int[length];
//the index of current center, the index of right bound of current palindrome
int center = 0, right_bound = 0;
for(int i = 1; i < length-1; ++i){
//the mirror position of current position i
int i_mirror = 2 * center - i;
//if the current right bound is greater than i, then we set
//p[i] to the min of p[i_mirror] and right_bound-i
//For example:
//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
//^ # a # b # a # b # a # b # $
//0 0 1 0 3 0
//assume center is 4, and right_bound is 7, and current i is 6
//i_mirror is 2, then p[i] will be 1
//Another case:
//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
//^ # b # a # b # c # b # a # b # c # b # a # $
//0 0 1 0 3 0 1 0 7 0 1 0 9 0 1 0
//assume center is 12, and right_bound is 21, and current i is 16
//i_mirror is 8, then p[i] will be 5 but not 7
p[i] = (right_bound > i) ? min(right_bound-i, p[i_mirror]) : 0;
//Expand palindrome centered at i
while(curr[i + 1 + p[i]] == curr[i - 1 - p[i]]){
p[i]++;
}
//If palindrome centered at i expand across right bound,
//adjust center based on expanded palindrome
if(i + p[i] > right_bound){
center = i;
right_bound = i + p[i];
}
}
//Find the maximum element in p
int max_len = 0;
int center_index = 0;
for(int i = 1; i < length-1; ++i){
if(p[i] > max_len){
max_len = p[i];
center_index = i;
}
}
//Clean array p
delete[] p;
return s.substr((center_index - 1 - max_len)/2, max_len);
}
Python Code:
#func: find the longest palindrome substring based on the current center
#@param s: the input string
#@param center_l: the index of left centroid
#@param center_r: the index of right centroid
#@return: the longest palindrome substring
def longest_palindrome_center(s, center_l, center_r):
assert 0 <= center_l < len(s)
assert 0 <= center_r < len(s)
assert center_l <= center_r
while center_l >= 0 and center_r < len(s) and s[center_l] == s[center_r]:
center_l -= 1
center_r += 1
return s[center_l+1: center_r]
#func: find the longest palindrome substring in the input string
#@param s: the input string
#@return: the longest palindrome substring
#complexity: time O(n^2), space O(n)
def longest_palindrome(s):
#Corner Case: the string is none
if not s:
return ''
#Initialize the result to the first element of the string
result = s[0]
for i in xrange(len(s)-1):
#get the palindrome of odd length
palindrome_odd = longest_palindrome_center(s, i, i)
result = palindrome_odd if len(palindrome_odd) > len(result) else result
#get the palindrome of even length
palindrome_even = longest_palindrome_center(s, i, i+1)
result = palindrome_even if len(palindrome_even) > len(result) else result
return result
Python Code:
#func: preprocessing for manacher algorithm
#example: aba ==> ^#a#b#a#$
#@param s: input string s
#@return: string after preprocessing
def manacher_helper(s):
#Coner Case:the string is none
if not s:
return '^$'
result = '^'
for char in s:
result += '#' + char
result += '#$'
return result
#func: find the longest palindrome substring using Manacher's algorithm
#@param s: input string s
#@return: longest palindrome substring
#complexity: time O(n), space O(n)
def longest_palindrome(s):
#string after preprocessing
curr = manacher_helper(s)
#auxiliary list
p = len(curr) * [0]
#the index of current center
center = 0
#the index of right bound of the current palindrome
right_bound = 0
for i in xrange(1, len(curr)-1):
#the mirror position of current position i
i_mirror = 2*center - i;
#if the current right bound is greater than i, then we set
#p[i] to the min of p[i_mirror] and right_bound-i
#For example:
#0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
#^ # a # b # a # b # a # b # $
#0 0 1 0 3 0
#assume center is 4, and right_bound is 7, and current i is 6
#i_mirror is 2, then p[i] will be 1
#Another case:
#0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
#^ # b # a # b # c # b # a # b # c # b # a # $
#0 0 1 0 3 0 1 0 7 0 1 0 9 0 1 0
#assume center is 12, and right_bound is 21, and current i is 16
#i_mirror is 8, then p[i] will be 5 but not 7
p[i] = min(right_bound-i, p[i_mirror]) if right_bound > i else 0
#Expand palindrome centered at i
while curr[i+1+p[i]] == curr[i-1-p[i]]:
p[i] += 1
#If palindrome centered at i expand across right bound
#adjust current center based on expanded palindrome
max_len = 0
center_index = 0
for i in xrange(1, len(curr)-1):
if p[i] > max_len:
max_len = p[i]
center_index = i
return s[(center_index-1-max_len)/2 : (center_index-1+max_len)/2]
Reference Link:
1.Longest Palindromic Substring Part I: http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
2.Longest Palindromic Substring Part II: http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
3.Longest palindromic substring: http://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher.27s_Algorithm_for_Finding_a_Longest_Palindrome_in_a_String
No comments:
Post a Comment