BiruLyu
5/24/2017 - 5:46 PM

## 5. Longest Palindromic Substring.java

``````class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return '';

# Use dynamic programming
dp = [[False for i in range(len(s))] for i in range(len(s))];
# define dp[i][j] is whether subtring from i to j is palindrome or not

maxlength = 0;
res = ""

for i in range(len(s) - 1, -1,-1):
for j in range(i,len(s)):
if s[i] == s[j] and ( j - i <= 2 or dp[i + 1][j - 1]) :
dp[i][j] = True;

if j - i + 1 > maxlength:
maxlength = j - i + 1;
res = s[i : j + 1];

return res;``````
``````public class Solution {
public String longestPalindrome(String s) {

String res = "";
int resLen = 0;

int len = s.length();
int[][] dp = new int[len][len];

for(int i = len - 1; i >= 0; i--){
for(int j = i; j < len; j++){
if(s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1] == 1)){
////先判断 j - i < 2，否则 i = j = len - 1 时下标溢出
dp[i][j] = 1;

if(j - i + 1 >= resLen){ //"abcd" the answer is "a"!!!!!
resLen = j - i + 1;
res = s.substring(i, j + 1);
}
}
}
}
return res;
}
}``````