題目
回文串的特點(diǎn)是署照，逆序輸出和正序輸出是一樣的。
所以這道題可以轉(zhuǎn)化為：如果將此字符串逆序輸出吗浩，那么兩個(gè)字符串的最長公共子序列將是最長的回文字符串建芙，那么剩余的值將是要刪除的字符個(gè)數(shù)。
經(jīng)典 LCS 算法題：POJ 1458 Common Subsequence 最長公共子序列（LCS）
LCS運(yùn)行軌跡圖
來自算法導(dǎo)論
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
/**
* Q: 為什么這個(gè)數(shù)組每次使用都不需要清空懂扼？
* A: 因?yàn)閿?shù)組最上邊的一行全部為 0 && 最左邊的一列也全部為 0 禁荸，
* 而后續(xù)的值都是根據(jù)這一行一列來定值的。
*/
private static int[][] maxLen = new int[1000][1000];
private static int work(String str) {
char[] ch = str.toCharArray();
char[] ch2 = new StringBuilder(str).reverse().toString().toCharArray();
int length = ch.length;
int length2 = ch2.length;
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= length2; j++) {
if (ch[i - 1] == ch2[j - 1]) {
maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
} else {
maxLen[i][j] = Math.max(maxLen[i][j - 1], maxLen[i - 1][j]);
}
}
}
return length - maxLen[length][length2];
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
String inputStr;
while (in.hasNext()) {
inputStr = in.next();
out.println(work(inputStr));
}
out.flush();
}
}
