5. 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.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:

Input: “cbbd”
Output: “bb”

Solution

  1. Brute Force
    维护区间[i,j], 对于每一个ij都判断一下是否为回文。
  2. DP(多个解中找最优解)
    状态转移方程:dp[i][j] = (dp[i+1][j-1] || i+1 > j-1) && s[i] == s[j], dp[i][j]表示区间为[i,j]的子串是否是回文数。
    细节:
    1. i,j分别从n-1开始递减,因为计算dp[i][j]的时候要保证dp[i+1][j-1]已经计算完毕。

Complexity

O(N^3) O(1)
O(N^2) O(N^2)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) return "";
int n = s.length(), start = 0, end = 0;
boolean dp[][] = new boolean[n][n];
for(int i=n - 1; i >= 0; --i){
for(int j = n - 1; j >= i; --j){
dp[i][j] = ( i+1 > j-1 || dp[i+1][j-1]) && s.charAt(i) == s.charAt(j);
if(dp[i][j] && j - i > end - start){
start = i; end = j;
}
}
}
return s.substring(start, end + 1);
}