构造回文

来源：

腾讯 2017 暑期实习生编程题

构造回文

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

输入：

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

输出：

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

输入示例：

abcda
google

输出示例：

2
2

Coding：

import java.util.Scanner;

/**
 * Created by Ziyun on 2017/4/2.
 */

public class Tencent_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String rawStr = sc.nextLine();
            int result = minDel(rawStr);
            System.out.println(result);
        }
    }

    /**
     * 求从一个字符串中最少删除几个字符能得到一个最长的回文串
     * 思路：回文串的特点在于将字符串逆转后得到的字符串和原串相同，所以可以利用这个特点加以求解。
     *      (1)将原字符串逆转得到一个逆转字符串；
     *      (2)计算原字符串和逆转字符串的最长公共子序列；
     *      (3)原字符串长度减去最长公共子序列的长度就是最少删除的字符串个数；
     *
     * @param str：待计算的字符串
     * @return：最少需要删除的字符个数
     */
    private static int minDel(String str) {
        String reverseStr = new StringBuilder(str).reverse().toString();    // 逆转字符串
        int len = str.length();

        // 动态规划求最长公共子序列长度
        int[][] dp = new int[len + 1][len + 1];
        // 注意起始位置
        for (int i = 1; i < dp.length; ++i) {
            for (int j = 1; j < dp[0].length; ++j) {
                dp[i][j] = str.charAt(i - 1) == reverseStr.charAt(j - 1) ? dp[i - 1][j - 1] + 1 :
                        Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return len - dp[len][len];    // dp[len][len] 即为原串与逆序串的最长公共子序列长度
    }
}