分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter
package live.every.day.ProgrammingDesign.CodingInterviewGuide.String; /** * 添加最少字符使字符串整体都是回文字符串 * * 【题目】 * 给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。 * * 【进阶题目】 * 给定一个字符串str，再给定str的最长回文子序列字符串strlps，请返回在添加字符最少的情况下，让str整体都是回文字符串的一 * 种结果。进阶问题比原问题多了一个参数，请做到时问复杂度比原问题的实现低。 * * 【难度】 * 困难 * * 【解答】 * 原问题。 * * 在求解原问题之前，我们先来解决下面这个问题，如果可以在str的任意位置添加字符，最少需要添几个字符可以让str整体都是回文 * 字符串。这个问题可以用动态规划的方法求解。如果str的长度为N，动态规划表是一个NxN的矩阵记为dp[][]。dp[i][j]值的含义 * 代表子串str[i..j]最少添加几个字符可以使str[i..j]整体都是回文串。那么，如何求dp[i][j]的值呢？有如下三种情况： * * １.如果字符串str[i..j]只有一个字符，此时dp[i][j]=0，这是很明显的，如果str[i..j]只有一个字符，那么str[i..j]已经是 * 回文串了，自然不必添加任何宇符。 * ２.如果字符串str[i..j]只有两个字符。如果两个字符相等，那么dp[i][j]=0。如果两个字符不相等，那么dp[i][j]=1。 * ３.如果字符串str[i..j]多于两个字符。如果str[i]==str[j]，那么dp[i][j]=dp[i+1][j-1]。如果str[i]!=str[j]，要 * 让str[i..j]整体变为回文串有两种方法，一种方法是让str[i..j-1]先变成回文串，然后在左边加上字符str[j]，就是 * str[i..j]整体变成回文串的结果。另一种方法是让str[i+1..j]先变成回文串，然后在右边加上字符str[i]，就是str[i..j] * 整体变成回文串的结果。两种方法中哪个代价最小就选择哪个，即dp[i][j]=min{dp[i][j-1],dp[i+1][j]}+1。 * * 既然dp[i][j]值代表子串str[i..j]最少添加几个字符可以使str[i..j]整体都是回文串，所以根据上面的方法求出整个dp矩阵之 * 后，我们就得到了str中任何一个子串添加几个字符后可以变成回文串。具体请参看如下代码中的getDP方法。 * * 下面介绍如何根据dp短阵，求在添加字符最少的情况下，让str整体都是回文字符串的一种结果。首先，dp[0][N-1]的值代表整个字 * 符串最少需要添加几个字符，所以，如果最后的结果记为字符串res，res的长度=dp[0][N-1]+str的长度，然后依次设置res左右 * 两头的字符。具体过程如下： * * １.如果str[i..j]中str[i]==str[j]，那么str[i..j]变成回文串的最终结果=str[i]+str[i+1..j-1]变成回文串的结果 * +str[j]，此时res左右两头的字符为str[i]（也是str[j]），然后继续根据str[i+1..j-1]和矩阵dp来设置res的中间部分。 * ２.如果str[i..j]中str[i]!=str[j]，看dp[i][j-1]和dp[i+1][j]哪个小。如果dp[i][j-1]更小，那么str[i..j]变成 * 回文串的最终结果=str[j]+str[i..j-1]变成回文串的结果+str[j]，所以此时res左右两头的字符为str[j]，然后继续根据 * str[i..j-1]和矩阵dp来设置res的中间部分。而如果dp[i+1][j]更小，那么str[i..j]变成回文串的最终结果= * str[i]+str[i+1..j]变成回文串的结果+str[i]，所以此时res左右两头的字符为str[i]，然后继续根据str[i+1..j]和矩阵 * dp来设置res的中间部分。如果一样大，任选一种设置方式都可以得出最终结果。 * ３.如果发现res所有的位置都已设置完毕，过程结束。 * * 原问题解法的全部过程请参看如下代码中的getPalindrome1方法。 * * 求解dp矩阵的时间复杂度为O(N^2)，根据str和dp矩阵求解最终结果的过程为O(N)，所以原问题解法中总的时间复杂度为O(N^2)。 * * @author Created by LiveEveryDay */ public class AddMinCharsMakePalindrome1 { public static int[][] getDP(char[] str) { int[][] dp = new int[str.length][str.length]; for (int j = 1; j < str.length; j++) { dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1; for (int i = j - 2; i > -1; i--) { if (str[i] == str[j]) { dp[i][j] = dp[i + 1][j - 1]; } else { dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1; } } } return dp; } public static String getPalindrome1(String str) { if (str == null || str.length() < 2) { return str; } char[] chas = str.toCharArray(); int[][] dp = getDP(chas); char[] res = new char[chas.length + dp[0][chas.length - 1]]; int i = 0; int j = chas.length - 1; int resl = 0; int resr = res.length - 1; while (i <= j) { if (chas[i] == chas[j]) { res[resl++] = chas[i++]; res[resr--] = chas[j--]; } else if (dp[i][j - 1] < dp[i + 1][j]) { res[resl++] = chas[j]; res[resr--] = chas[j--]; } else { res[resl++] = chas[i]; res[resr--] = chas[i++]; } } return String.valueOf(res); } public static void main(String[] args) { String str = "A1B21C"; System.out.printf("The palindrome is: %s", getPalindrome1(str)); } } // ------ Output ------ /* The palindrome is: AC1B2B1CA */
