You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 005.最长回文串-Longest Palindromic Substring

Longest Palindromic Substring

## Analysis: Dynamic Programming

To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes.

Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.

Define $P(i,j)$ as following:

$$P(i, j)=\left{ \begin{array}{lr} \text{true,}&\quad\text{if the substring } S_i \dots S_j \text{ is a palindrome} \ \text{false,} &\quad\text{otherwise.} \end{array} \right.$$

Therefore,

$$P(i,j)=(P(i+1,j−1) \land S_i==S_j)$$

The base cases are:

$$P(i, i) = true$$

$$P(i, i+1) = (S_i == S_{i+1})$$

Complexity Analysis

• Time complexity : $O(n^2)$. This gives us a runtime complexity of $O(n^2)$.
• Space complexity : $O(n^2)$. It uses $O(n^2)$ space to store the table.

[scode type="yellow"]

• 这道题中由动态规划的递推公式可知，在矩阵中，当前位置由其右下角的单元及字符串本身决定。
• 因此在自底向顶的设计中，应该优先填充左下角的部分
• i--
• j++
其中 i 表示横，j 表示纵
[/scode]

## My solution: 38ms

class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len == 0)   return "";
char[] str = s.toCharArray();
boolean[][] dp = new boolean[len][len];
// default: ∀i∀j(dp[i][j] == false)
int maxLen = 0;
int maxLeft = 0;
int maxRight = 0;
/* base case: */
for (int i = 0; i < len; i++) {
dp[i][i] = true;
if (i + 1 < len && str[i+1] == str[i]) {
dp[i][i+1] = true;
maxLen = 1;
maxLeft = i;
maxRight = i + 1;
}
}
/* using dynamic programming */
// enumerate right boundry of the substring
for (int j = 0; j < len; j++) {
// enumerate left boundry of the substring
for (int i = j - 2; i >= 0; i--) {
dp[i][j] = str[i] == str[j] && dp[i+1][j-1];
if(dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
maxLeft = i;
maxRight = j;
}
}
}
return s.substring(maxLeft, maxRight + 1);
}
}