【dp】构造回文详解编程语言

构造回文

题目

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

输入描述:

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

输出描述:

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

输入例子1:

abcda
google

输出例子1:

2
2

题解

这道题是寻找最大子序列题型（LCS）的变种，我们可以将字符串反转，求正序和倒序字符串的lcs，寻找到的序列就是可以最长的回文序列，然后用原字符串的长度减去这个lcs的长度，就是要删除的字符个数。

如何寻找lcs？这是一个老生常谈的问题，不再赘述。尚不理解的小伙伴可以移步：IT虾米网

下面是我的代码。比较坑的一点是，获取输入的字符串时要使用sc.nextLine()而不能用sc.next()，否则会报数组越界，个人理解是输入里面可能有空格，要用nextLine()才可以完整地读取一行，next()不可以。

import java.util.*; 
public class Main{
 
//在正序、倒序中找到LCS即可 
public static void main(String[] args){
 
Scanner sc = new Scanner(System.in); 
while( sc.hasNextLine() ){
 
String str1 = sc.nextLine(); 
String str2 = new StringBuilder(str1).reverse().toString(); 
int lcs = getLCS(str1, str2); 
System.out.println(str1.length()-lcs); 
} 
sc.close(); 
} 
//获取最大回文串长度 
private static int getLCS(String str1, String str2){
 
int len1 = str1.length(); 
int len2 = str2.length(); 
if( len1==0 || len2==0 ) return 0; 
int[][] dp = new int[len1+1][len2+1]; 
for( int i=1; i<=len1; i++ ){
 
for( int j=1; j<=len2; j++ ){
 
if( str1.charAt(i-1)==str2.charAt(j-1) ){
 
dp[i][j] = dp[i-1][j-1] + 1; 
}else{
 
//两个字符不相等，那么根据dp思想， 
//最长子序列长度就是dp[i-1][j]和dp[i][j-1]中的较大值 
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); 
} 
} 
} 
return dp[len1][len2]; 
} 
}