5. Longest Palindromic Substring
Tags: ‘String’, ‘Dynamic Programming’
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd" Output: "bb"
Solution 1 DP
$O(n^2)$ time $O(n^2)$ space 动态规划
- Memorization:
dp[i][j]-> ifsubstring(1, j)is parlindromic - State transition:
-
if
j - i <= 2thendp[i][j] = s.charAt(i) == s.charAt(j) -
else
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1]
-
注意：只考虑图的右上半， 所以i递减，j递加
public String longestPalindrome(String s) {
String result = "";
boolean[][] dp = new boolean[s.length()][s.length()];
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (j - i <= 2) { // 1 2 3 directly check i and j no need to consider inside
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
}
if (dp[i][j] && (result == null || j - i + 1 > result.length())) {
result = s.substring(i, j + 1);
}
}
}
return result;
}
Solution 2 Expand Around Center
$O(n^2)$ time $O(1)$ space 87% 100%
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}