Longest Palindromic Substring
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(n2) time is acceptable. Can you do it in O(n) time.
Solution1. DP O(n^2)
定义函数
P[i,j] = 字符串区间[i,j]是否为palindrome.
首先找个例子,比如S=”abccb”,
S= a b c c b
Index = 0 1 2 3 4
P[0,0] =1 //each char is a palindrome
P[0,1] =S[0] == S[1] , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3], P[3,3]=1
………………….
由此就可以推导出规律
P[i,j] = 1 if i ==j
= S[i] ==S[j] if j = i+1
= S[i] == S[j] && P[i+1][j-1] if j>i+1
实现如下:
public String longestPalindrome(String s) { if (s == null) { return ""; } String res = ""; int n = s.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { if (i - j <= 2) { dp[j][i] = s.charAt(i) == s.charAt(j); } else { dp[j][i] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1]; } if (dp[j][i]) { if (i - j + 1 > res.length()) { res = s.substring(j, i + 1); } } } } return res; }
Solution2: Check both aba and abba 2 cases. O(n^2)
public String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } String result = ""; //1. if it is like 'aba' for (int i = 0; i < s.length(); i++) { int count = 0; while (i - count >= 0 && i + count < s.length() && s.charAt(i - count) == s.charAt(i + count)) { count++; } String palindrome = s.substring(i - count + 1, i + count); if (palindrome.length() > result.length()) { result = palindrome; } } //2. if it is like 'abba', the pivot would be the interval between i and i+1 for (int i = 0; i < s.length() - 1; i++) { int count = 1; while (i - count + 1 >= 0 && i + count < s.length() && s.charAt(i - count + 1) == s.charAt(i + count)) { count++; } if (count > 1) { String palindrome = s.substring(i - count + 2, i + count); if (palindrome.length() > result.length()) { result = palindrome; } } } return result; }