# LeetCode05

LeetCode05

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Output: “bab”
Note: “aba” is also a valid answer.

dp[i][j]=truetruefalse,ifdp[j+1][i1]=trueandstr[i]==str[j],ij<=2andstr[i]==str[j],elsedp[i][j]={true,ifdp[j+1][i−1]=trueandstr[i]==str[j]true,i−j<=2andstr[i]==str[j]false,else

class Solution {
public String longestPalindrome(String s) {
int len = s.length();
boolean[][] dp = new boolean[len][len];
int max = 0;
int start = 0;
int end = 0;
for(int i = 0; i < len; i++){
for(int j = 0; j <= i; j++){
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i - 1])){
dp[j][i] = true;
}
if(dp[j][i] && max < (i - j + 1)){
max = i - j + 1;
start = j;
end = i+1;
}
}
}
return s.substring(start, end);
}
}

|
4月前
leetcode-1447：最简分数
leetcode-1447：最简分数
42 0
|
4月前
|
Java
leetcode-474：一和零
leetcode-474：一和零
30 0

67 0
leetcode 827 最大人工岛
leetcode 827 最大人工岛
56 0
leetcode 283 移动零
leetcode 283 移动零
50 0
|

leetcode第43题

77 0
|

leetcode第49题

143 0
|

leetcode第40题

61 0
leetcode第38题

77 0
leetcode第46题

61 0