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.
Example
Given the string = "abcdzdcab", return "cdzdc".
Challenge
O(n^2) time is acceptable. Can you do it in O(n) time.
Tags
String
Related Problems
Easy Valid Palindrome 22 %
Medium Longest Palindromic Substring 26 %
Medium Palindrome Partitioning II 22 %
这种方法基本思想是遍历数组，以其中的1个元素或者2个元素作为palindrome的中心，通过辅助函数，寻找能拓展得到的最长子字符串。外层循环 O(n)，内层循环O(n)，因此时间复杂度 Time O(n^2)，相比动态规划二维数组存状态的方法，因为只需要存最长palindrome子字符串本身，这里空间更优化：Space O(1)
public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
if(s == null || s.length() <= 1) {
return s;
}
int len = s.length();
int maxLen = 1;
boolean [][] dp = new boolean[len][len];
String longest = null;
for(int k = 0; k < s.length(); k++){
for(int i = 0; i < len - k; i++){
int j = i + k;
if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])){
dp[i][j] = true;
if(j - i + 1 > maxLen){
maxLen = j - i + 1;
longest = s.substring(i, j + 1);
}
}
}
}
return longest;
}
}
DP - Time O(n^2), Space O(n^2)
外层循环区间长度，内层循环区间起点
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
String longestPStr = "";
int strLen = s.length();
boolean[][] dp = new boolean[strLen][strLen];
for (int len = 1; len <= strLen; len++) {
for (int i = 0; i < strLen; i++) {
int j = i + len - 1;
if (j >= strLen) {
break;
}
dp[i][j] = (len <= 2 || dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j);
if (dp[i][j] && len > longestPStr.length()) {
longestPStr = s.substring(i, j + 1);
}
}
}
return longestPStr;
}
}
*Another implementation DP - Time O(n^2), space O(n^2)
外层循环区间起点，内层循环区间终点
递推公式中可以看到，首先知道了 i + 1 才会知道 i ，所以只需要倒着遍历i就行了。
类似的，先知道j - 1才知道j，因此顺着遍历j
In the state transfer function: j - i < 2 could also be j - i <= 2
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表长度减去 1
if (dp[i][j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
Space Optimized DP - Time O(n^2), space O(n)
public String longestPalindrome7(String s) {
int n = s.length();
String res = "";
boolean[] P = new boolean[n];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) {
P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
if (P[j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
Expand Around Center - Time O(n^2) Space O(1)
public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
// get longest palindrome with center of i
String tmp = helper(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// get longest palindrome with center of i, i+1
tmp = helper(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// Given a center, either one letter or two letter,
// Find longest palindrome
public String helper(String s, int begin, int end) {
while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
begin--;
end++;
}
return s.substring(begin + 1, end);
}
}
Another expand-center implementation
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
String longest = "";
for (int i = 0; i < s.length(); i++) {
// single center
String tmp = helper(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// dual center
tmp = helper(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// center expand helper function
// @return longest string centered at i, j
private String helper(String s, int i, int j) {
if (i >= s.length() || j >= s.length()) {
return "";
}
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return s.substring(i + 1, j);
}
}
Expand Center - O(n^2) time, O(1) space
@jinwu
7 ms, faster than 99.69%
public class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2)
return s;
for (int i = 0; i < len-1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i+1); //assume even length.
}
return s.substring(lo, lo + maxLen);
}
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}}