LeetCode 5 题解
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
代码语言：javascript复制输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
代码语言：javascript复制输入: "cbbd"
输出: "bb"
思路：动态规划
动态转移方程
dp[i][j] = dp[i 1][j-1] && (s[i]==s[j])
边界条件：
当只有一个字符时候dp[i][i 0] = true
当有两个字符时：dp[i][i 1] =(s[i]==s[i 1])
代码语言：javascript复制public class LeetCode5 {
public String longestPalindrome(String s) {
/**
* 动态转移方程
* dp[i][j] = dp[i 1][j-1] && (s[i]==s[j])
*
* 边界条件：
* l 表示 字符长度
* dp[i][j] = true;
* l = 1 时 dp[i][j] = (s[i]== s[j])
*/
char[] charArray = s.toCharArray();
int len = s.length();
boolean[][] dp = new boolean[len][len];
String ans = "";
for(int l = 0; l < len; l ){// 长度为0 1 到len-1
for(int i = 0; i < len;i ){// 开始位置是 i
int j = i l; // 结束位置是j
if(j >= len ) break;
if(l == 0){ // 边界条件，单个字段是回文
dp[i][j]= true;
}else if(l == 1){// 边界条件 两个字符需要判断
dp[i][j] = (charArray[i] == charArray[i 1]);
}else{
dp[i][j] = dp[i 1][j-1]&&(charArray[i]==charArray[j]);
}
if(dp[i][j] && l 1 > ans.length()){
ans = s.substring(i,j 1); // 包含位置 j
}
}
}
return ans;
}
/**
* @param args
*/
public static void main(String[] args) {
// String s = "babad";
// String s = "cbbd";
String s = "a";
System.out.println(new LeetCode5().longestPalindrome(s));
}
}
