构造回文

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子1:

abcda google 输出例子1:

2 2

思路1（中心扩展）： 以str的第i个位置上的元素作为中心点或者回文字符串的左边最中间点；m向左边检索，n向右边检索；得到最长回文字符串；

遍历i，得到最长的回文字符串；

输出为原字符串长度减去最长回文字符串长度。

错误：

cdeabeda

当以b为中心点，实际上想找的数值是debed对应的5，但是代码会找到aba，就是前面的a检索到后面的a，下一步就会把ed跳过去了；

有相似思路解出来的同学请求指教！！！

代码：

import java.util.Scanner; public class Main { /** * str中以i为中心的最大回文字符串; * 若最终长度为偶数，开始位置算到左边 * @param str * @param i * @return */ public static int findLongst(String str,int i) { int m = i; int ns = i + 1;//每次接着上次搜索的位置开始搜索 String sub = "" + str.charAt(i); for(;m>=0;m--) for(int n = ns;n<str.length();n++) { if(str.charAt(m)==str.charAt(n)) { ns = n + 1; if(m == i) sub += str.charAt(n); else sub = str.charAt(m) + sub + str.charAt(n); break; } } return sub.length() ; } public static void main(String[] args) { @SuppressWarnings("resource") Scanner scan = new Scanner(System.in); while(scan.hasNextLine()) { String s = scan.nextLine(); int len = 0; for(int i = 0;i<s.length();i++) { int temp = findLongst(s,i); if(temp>len) len = temp; } System.out.println(s.length()-len); } } }

给出的批复是：

case通过率为0.00% 测试用例: zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk 对应输出应该为: 516 你的输出为: 675

思路2（动态规划）：

对于字符串s，建立一个int[][] dp = new int[s.length()][s.length()]; dp[start][end] 对应start~end位置的子串sub所包含的最长回文子字符串的长度。

1、s[start] == s[end]    

    i)  包含的最长回文子字符串是start+1 ~ end - 1对应的最长回文子字符串加上start和end位置的额字符，这时候对应dp[start][end]  = dp[start+1][end-1] +2；

    ii)  包含的最长回文子字符串是start+1 ~ end 对应的最长回文子字符，对应dp[start][end]  = dp[start+1][end]；

    iii) 包含的最长回文子字符串是start~ end-1 对应的最长回文子字符，对应dp[start][end]  = dp[start][end-1]；

2、s[start] != s[end]    

    i)  包含的最长回文子字符串是start+1 ~ end - 1对应的最长回文子字符串，对应dp[start][end]  = dp[start+1][end-1] ；

    ii)  包含的最长回文子字符串是start+1 ~ end 对应的最长回文子字符，对应dp[start][end]  = dp[start+1][end]；

    iii) 包含的最长回文子字符串是start~ end-1 对应的最长回文子字符，对应dp[start][end]  = dp[start][end-1]；

即对于每个位置，有3条路径到达：

取三条路劲对应的最大值作为当前dp[start][end] 的最大值；

代码实现：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNextLine()) { String s = scan.nextLine(); int l = LenOfLPS(s); System.out.println(s.length() - l); } // String s = "zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk"; String s = "cabdaba"; // int l = LenOfLPS(s); // // System.out.println(s.length() - l); } public static int LenOfLPS(String s) { int[][] dp = new int[s.length()][s.length()]; //对角线位置 for(int i = 0;i<s.length();i++) { dp[i][i] = 1; } //end - start = 1的位置 for(int i = 0;i<s.length()-1;i++) if(s.charAt(i) == s.charAt(i+1)) dp[i][i+1] = 2; else dp[i][i+1] = 1; //end - start = i(i>1)的位置 for(int i = 2;i<s.length();i++) for(int start = 0;start<s.length()-i;start++) { // System.out.println(); int end = start + i; if(s.charAt(start) == s.charAt(end)) dp[start][end] = max(dp[start+1][end-1] + 2,dp[start][end-1],dp[start+1][end]); else dp[start][end] = max(dp[start+1][end-1],dp[start][end-1],dp[start+1][end]); } return dp[0][s.length() - 1]; } public static int max(int x1,int x2,int x3) { int max = x1; if(max<x2) max = x2; if(max<x3) max = x3; return max; } } 这个是通过全部测试用例的。