一、题目回文字符串是指字符串，从左向右读和从右向左读完全一样。 例如，“a”、“aba”、“abba”。
对于字符串，子字符串是指连续的段字符串，子字符串是可以不连续的段字符串。
最长回文子串和http://www.Sina.com/(longestpalindromicsubsequence )指向其中一个字符串，说它包含最长的回文子串和回文子串。
例如，字符串“ABCDDCEFA”、其最长回文子序列即“CDDC”、最长回文子串即“ACDDCA”。
二、最长回文子串1 .构想首先，这类问题用包罗万象的方法判断是否是回文子串，筛选最长的东西效率不高。 我们使用最长回文子序列的策略来解决它。 先从子问题开始，保存子问题的解。 之后，在解决下一个问题时，重复利用子问题的解，可以非常有效率地进行提示。
由于要求最长回文部分列是连续的，所以可以假设j为部分列的开始坐标，I为部分列的终点坐标。 这里，I和j都为0以上且小于字符串长度length，j=i。 这样的子串的长度可以用i - j 1表示。
我们从长1的子串开始依次遍历。 长度为1的子串必须是回文，其长度为1。 只要长度为2的子串被顺序扫描，且str[i]等于str[j]，则它是回文，其长度为2，并且长度大于2的子串满足是回文子串的性质，因此str[i]是str[j] 由于必定是回文部分列，所以使用存储以j为部分列的开始坐标、以I为部分列的终点坐标的部分列是否是回文的排列
2 .代码公共类主{ publicstaticvoidmain (string [ ] args ) { String s='cabbaeeaf '； system.out.println(getLPS )； } publicstaticstringgetlps (strings ) { char[] chars=s.toCharArray )； int length=chars.length； //一维参数表示开始位置坐标，二维参数表示终点坐标//lps[j][i]表示j为开始坐标，I为终点坐标，回文子串boolean [ ] [ ] LPS=new boolean [ length ] int maxLen=1； //记录最长回文部分列最长长度int start=0记录最长回文部分列的开头位置for (inti=0； i length； I ) for(intj=0； j=i； j ) ) if(I-j2 ) ) /子字符串长度小于2时lps[j][i]=chars[i]==chars[j]； }如果} else { //，j]是回文子串，则[j 1，i-1]也一定是回文子串LPS [ j ] [ I ]=LPS [ J1 ] [ I-1 ] [ chars [ I ]==chars [ j ] 开始=j； }}returns.substring(start，start maxLen )； (三、最长回文部分列1 )构想部分列的问题比部分列更复杂。 因为可以不连续。 因此，如果包括在内，问题的规模就会变得非常大。 我们仍然选择使用动态规划进行解决。
首先，假设str[0 . n-1]是给定长度为n的字符串，以0为开始坐标，用lps(0，n-1 )表示长度为n-1的最长回文部分序列的长度。 那我们呢
要从子问题开始入手，即我们一次遍历长度 1 到 n-1 的子串，并将子串包含的 最长回文子序列的长度 保存在 lps 的二维数组中。遍历过程中，回文子序列的长度一定有如下性质：
如果子串的第一个元素 str[j] 和最后一个元素 str[i+j] 相等，那么 lps[j, i+j] = lps[j+1, i+j-1] + 2，其中 lps[j+1, i+j-1] 表示去掉两头元素的最长子序列长度。如果两端的元素不相等，那么lps[j, i+j] = max(lps[j][i+j-1], lps[j+1][i+j])，这两个表示的分别是去掉末端元素的子串和去掉起始元素的子串。 2. 代码 public class Main { public static void main(String[] args) { String s = "cabbeaf"; System.out.println(getLPS(s)); } public static int getLPS(String s) { char[] chars = s.toCharArray(); int length = chars.length; // 第一维参数表示起始位置的坐标，第二维参数表示长度，使用 0 表示长度 1 int[][] lps = new int[length][length]; for (int i = 0; i < length; i++) { lps[i][i] = 1; // 单个字符的最长回文子序列长度为1，特殊对待一下 } // (i + 1) 表示当前循环的子字符串长度 for (int i = 1; i < length; i++) { // j 表示当前循环的字符串起始坐标 for (int j = 0; i + j < length; j++) { // 即当前循环的子字符串坐标为 [j, i + j] // 所以第一个字符是 chars[j]，最后一个字符就是 chars[i + j] if (chars[j] == chars[i + j]) { lps[j][i + j] = lps[j + 1][i + j - 1] + 2; } else { lps[j][i + j] = Math.max(lps[j][i + j - 1], lps[j + 1][i + j]); } } } // 最大值一定在以0为起始点，长度为 length - 1 的位置 return lps[0][length - 1]; } }最后，这题只返回了最长回文子序列的长度，一般面试题中也只是要求返回长度即可。但是如果你也想知道最长回文子序列具体是啥，这可以额外添加一个变量记录最长回文子序列是哪些字符，例如维护一个键为 lps[j][i + j]，值为 String 的 map。