题目:给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000
示例 1:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案
方法一:
1 /* 2 * 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 3 * 示例 1: 4 输入: "babad" 5 输出: "bab" 6 注意: "aba" 也是一个有效答案 7 */ 8 public String longestPalindrome2(String s) { 9 if(s == null) { 10 throw new IllegalArgumentException("参数输入错误"); 11 } 12 if(s.length() <= 1) { 13 return s; 14 } 15 /*//该段代码可省略 16 if(s.length() == 2) { 17 if(s.charAt(0) == s.charAt(1)) { 18 return s; 19 }else { 20 return s.substring(0,1); 21 } 22 }*/ 23 int len = s.length(); 24 int start = 0; 25 int end = 0; 26 boolean[][] palimdrome = new boolean[len][len]; 27 //边界条件:1单个字符都为回文子串,2相邻的两个字符相同则为回文子串 28 for(int i=0; i<len; i++) { 29 palimdrome[i][i] = true; 30 if(i<len-1) { 31 if(s.charAt(i) == s.charAt(i+1)) { 32 palimdrome[i][i+1] = true; 33 start = i; 34 end = i + 1; 35 }else { 36 palimdrome[i][i+1] = false; 37 } 38 } 39 } 40 //最优子结构:根据对于字符串str,假设dp[i,j]=true表示str[i...j]是回文子串,那个必定存在dp[i+1,j-1]=true 41 //可以得到最优子结构 42 for(int l=2; l<len; l++) { //依次判断不同长度的子字符串是否是回文字符,长度从l+1=3(l=2)开始,4、5... 43 for(int i=0; i<len-l; i++){ //首字符位置不断右移 44 int j = i + l; 45 if(s.charAt(i) == s.charAt(j)) { 46 palimdrome[i][j] = palimdrome[i+1][j-1]; 47 if(palimdrome[i][j]) { 48 if((l) > (end - start)) { 49 start = i; 50 end = j; 51 } 52 } 53 }else { 54 palimdrome[i][j] = false; 55 } 56 } 57 } 58 return s.substring(start, end + 1); 59 }
推荐阅读:https://www.cnblogs.com/mini-coconut/p/9074315.html