首页 > 代码库 > six solutions to a single symmetrical problem
six solutions to a single symmetrical problem
Problem description:
given a string, find the longest palindrome string in it
Solution:
1.brute force
O(n^3)
just enumerate start and end of the substring and using head pointer and tail pointer to judge if it‘s a palindrome
2.enumerate center
but I failed to think of even-length palindrome
3.dp
so sorry for this part...
dp[i][j](i <= j) = 1 if a[i]...a[j] is a substring
= 0 else
then dp[i][i] = 1 for all i
dp[i][j] = (a[i] == a[j] && dp[i-1][j+1]) for j - i > 2;
dp[i][i+1] = (a[i] == a[i+1]);
since the matrix is n^2 and each element is written only once, O(n^2)
4.using suffix trees
reducing to O(nlogn)
perhaps refer to wiki might offer a good solution
5.Manacher‘s Algorithm
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html#comment-166993
6. using KMP algorithms
however,the solution is wrong since match part does not necessarily is a palindrome
but the point is worth thinking
http://blog.csdn.net/hopeztm/article/details/7932245
another problem:what if it aims to find the longest subsequence?