LeetCode 5 题解
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：
输入: "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])
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)); } }
