DeepSeek 一个字符串至少需要添加多少个字符能整体变成回文串 java实现

我们可以通过动态规划来解决这个问题，找到原字符串和其反转字符串的最长公共子序列（LCS），然后用原字符串长度减去LCS长度即为最少需要添加的字符数。

以下是完整的Java实现：

import java.util.Scanner;

public class MinInsertionsToPalindrome {

/**
* 方法1：动态规划 – 基于最长公共子序列
* 时间复杂度：O(n²)，空间复杂度：O(n²)
*/
public static int minInsertionsByLCS(String s) {
int n = s.length();
// 反转字符串
String reversed = new StringBuilder(s).reverse().toString();

// dp[i][j]表示s的前i个字符和reversed的前j个字符的LCS长度
int[][] dp = new int[n + 1][n + 1];

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i – 1) == reversed.charAt(j – 1)) {
dp[i][j] = dp[i – 1][j – 1] + 1;
} else {
dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1]);
}
}
}

// 最少添加字符数 = 原长度 – LCS长度
return n – dp[n][n];
}

/**
* 方法2：区间DP（更直观的回文解法）
* 时间复杂度：O(n²)，空间复杂度：O(n²)
*/
public static int minInsertionsByDP(String s) {
int n = s.length();
// dp[i][j]表示使子串s[i..j]变成回文需要添加的最少字符数
int[][] dp = new int[n][n];

// 从长度为2的子串开始计算
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n – len; i++) {
int j = i + len – 1;

if (s.charAt(i) == s.charAt(j)) {
// 首尾字符相同
if (len == 2) {
dp[i][j] = 0; // 两个相同字符已经是回文
} else {
dp[i][j] = dp[i + 1][j – 1];
}
} else {
// 首尾字符不同，可以在前面添加s[j]或在后面添加s[i]
dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j – 1]);
}
}
}

return n > 0 ? dp[0][n – 1] : 0;
}

/**
* 方法3：优化空间的DP（滚动数组）
* 时间复杂度：O(n²)，空间复杂度：O(n)
*/
public static int minInsertionsOptimized(String s) {
int n = s.length();
if (n <= 1) return 0;

int[] dp = new int[n];

for (int i = n – 2; i >= 0; i—) {
int prev = 0; // 保存dp[i+1][j-1]
for (int j = i + 1; j < n; j++) {
int temp = dp[j]; // 保存下一轮要用的prev

if (s.charAt(i) == s.charAt(j)) {
dp[j] = prev;
} else {
dp[j] = 1 + Math.min(dp[j], dp[j – 1]);
}

prev = temp;
}
}

return dp[n – 1];
}

/**
* 方法4：递归+备忘录（自顶向下）
*/
public static int minInsertionsMemo(String s) {
int n = s.length();
Integer[][] memo = new Integer[n][n];
return helper(s, 0, n – 1, memo);
}

private static int helper(String s, int i, int j, Integer[][] memo) {
if (i >= j) return 0;

if (memo[i][j] != null) {
return memo[i][j];
}

if (s.charAt(i) == s.charAt(j)) {
memo[i][j] = helper(s, i + 1, j – 1, memo);
} else {
int insertLeft = helper(s, i + 1, j, memo);
int insertRight = helper(s, i, j – 1, memo);
memo[i][j] = 1 + Math.min(insertLeft, insertRight);
}

return memo[i][j];
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入一个字符串: ");
String s = scanner.nextLine();

System.out.println("\\n输入字符串: " + s);
System.out.println("字符串长度: " + s.length());

System.out.println("\\n方法1 (基于LCS): " + minInsertionsByLCS(s) + " 个字符");
System.out.println("方法2 (区间DP): " + minInsertionsByDP(s) + " 个字符");
System.out.println("方法3 (优化空间): " + minInsertionsOptimized(s) + " 个字符");
System.out.println("方法4 (递归+备忘录): " + minInsertionsMemo(s) + " 个字符");

// 展示构造回文的过程
System.out.println("\\n构造回文示例:");
String palindrome = constructPalindrome(s);
System.out.println("原字符串: " + s);
System.out.println("可构造的回文: " + palindrome);
System.out.println("需要添加 " + (palindrome.length() – s.length()) + " 个字符");

scanner.close();
}

/**
* 辅助方法：构造一个回文串
*/
public static String constructPalindrome(String s) {
int n = s.length();
if (n == 0) return "";

StringBuilder result = new StringBuilder(s);
int i = 0, j = n – 1;

while (i < j) {
if (result.charAt(i) != result.charAt(j)) {
// 在j后面插入result.charAt(i)
result.insert(j + 1, result.charAt(i));
n++;
i++;
j++; // 因为插入了一个字符，j的位置后移
} else {
i++;
j—;
}
}

return result.toString();
}
}

算法解释

核心思路

最少添加字符数 = 字符串长度 – 最长回文子序列长度

方法对比

方法 时间复杂度 空间复杂度 特点
方法1 (LCS) O(n²) O(n²) 直观，易于理解
方法2 (区间DP) O(n²) O(n²) 直接解决回文问题
方法3 (优化空间) O(n²) O(n) 空间效率高
方法4 (递归) O(n²) O(n²) 自顶向下，逻辑清晰

示例运行

输入字符串: abca
字符串长度: 4

方法1 (基于LCS): 1 个字符
方法2 (区间DP): 1 个字符
方法3 (优化空间): 1 个字符
方法4 (递归+备忘录): 1 个字符

构造回文示例:
原字符串: abca
可构造的回文: acbca
需要添加 1 个字符

算法原理详解

以字符串 “abca” 为例：

关键点

可以根据实际需求选择不同的实现方法。对于较长的字符串，推荐使用方法3（优化空间的DP）。