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.
Analysis
This is a very basic dynamic programming problem. We use a 2-D boolean array P to save whether a substring of s is palindromic. We start from substring of length of 1 to length of length of s. If s[i] = s[j] and P[i+1][j-1] is true, we know that we need to update P[i][j] to true. In addition, if j – i <= 2, it means the length of this substring is only 1 or 2, so we can directly update P[i][j] to true.
To return the longest palindromic substring, we need to save the start point and the maximum length of the palindromic substring during our processing.
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class Solution { public String longestPalindrome(String s) { boolean[][] P = new boolean[s.length()][s.length()]; int max = 0; int start = 0; for (int k = 0; k < s.length(); k++) { for (int i = 0; i < s.length() - k; i++) { if (s.charAt(i) == s.charAt(i + k)) { if (k < 2 || P[i + 1][i + k - 1]) { P[i][i + k] = true; if (k > max) { max = k; start = i; } } } } } return s.substring(start, start + max + 1); } } |
In this code, in fact, (k + 1) is the length of the substring. Writing in this way will be more convenient.
Complexity
We need to check every substring in this string. The time complexity is $O(n^2)$, which is the same as the space complexity.