# 构造回文

[编程题]构造回文
• 热度指数：36597 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

```

```

```

```

```abcda
```

## 输出

```2
2
```
```#Python版
#思路：最长会文字序列：==  Str与reverse_Str的最长公共字序列
#注意：碰到了楼上Python解法同样的问题，没把循环过程放到name中，一直说是过90%
#然后超时，放进去就好了。猜一下：是不是给了程序入口能加快解析  # -*- coding:utf-8 -*-
import sys

def maxlcp(strs):
if strs==None or len(strs)==0:
return 0
lens = len(strs)
dp =[0] *lens
dp[0] = 1 if strs[0] == strs[lens-1] else 0
for i in range(lens):
pre = dp[0]
dp[0] = max(dp[0],1 if strs[i] == strs[lens-1] else 0)
for j in range(1,lens):
cur = dp[j]
dp[j] = max(dp[j],dp[j-1])
if strs[i] == strs[lens-1-j]:
dp[j] = max(dp[j],pre+1)
pre = cur

return dp[lens-1]

if __name__ == '__main__':
while True:
lens = len(line)
if not line:
break
maxLcp = maxlcp(line)
# print lens
# print maxLcp
print lens - maxLcp
```

```include<iostream>
#include<string>

using namespace std;
const int MAX_LENGTH = 1002;
int dynamic[MAX_LENGTH][MAX_LENGTH];

int min_palindrome(string s)
{
if(s.length() <= 1)
return 0;
for(int i=0; i<s.length(); ++i)
{
dynamic[i][i] = 0;
}
for(int l=2; l<=s.length(); ++l)
{
for(int s_ind=0; s_ind<=s.length()-l; ++s_ind)
{
if(s[s_ind] == s[s_ind+l-1])
dynamic[s_ind][s_ind+l-1] = s_ind+1<=s_ind+l-2 ? dynamic[s_ind+1][s_ind+l-2] : 0;
else
dynamic[s_ind][s_ind+l-1] = 1 + min(dynamic[s_ind+1][s_ind+l-1], dynamic[s_ind][s_ind+l-2]);
}
}
return dynamic[0][s.length()-1];
}

int main()
{
string s;
while(cin >> s)
{
cout << min_palindrome(s) << endl;
}
}```
python 版本，只能通过90%
```import sys
def min_palindrome(s):
if len(s) <= 1:
return 0
dynamic = [[0] * len(s)] * len(s)
for l in xrange(2, len(s)+1):
for s_ind in xrange(0, len(s)+1-l):
if s[s_ind] == s[s_ind + l-1]:
dynamic[s_ind][s_ind + l-1] = 0 if s_ind+1>s_ind + l-2 else dynamic[s_ind+1][s_ind + l-2]
else:
dynamic[s_ind][s_ind + l-1] = 1 + min(dynamic[s_ind+1][s_ind + l-1], dynamic[s_ind][s_ind + l-2])
return dynamic[0][len(s)-1]
for line in sys.stdin:
print min_palindrome(line.strip())```

```
import java.util.Scanner;

public class ConstructPlalindrome {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);

while(scan.hasNext()) {
String s = scan.nextLine();
System.out.println(s);
int len = lenghOfLCS(s, new StringBuffer(s).reverse().toString());
System.out.println(s.length() - len);
}

scan.close();
}

//动态规划求最长公共子序列的长度
public static int lenghOfLCS(String s1, String s2) {
char[] ch1 = s1.toCharArray();
char[] ch2 = s2.toCharArray();

int n1 = s1.length();
int n2 = s2.length();
int[][] table = new int[n1][n2];//所有元素默认初始化为0

if(ch1[0] == ch2[0]) table[0][0] = 1;

//单独计算s2与s1首字母之间的的LCS长度
for(int i = 1; i < n2; ++i) {
if(ch1[0] == ch2[i])
table[0][i] = 1;
else
table[0][i] = table[0][i-1];
}

//单独计算s1与s2首字母之间的LCS长度
for(int i = 1; i < n1; ++i) {
if(ch2[0] == ch1[i])
table[i][0] = 1;
else
table[i][0] = table[i-1][0];
}

//递推求解各个字符处的LCS
for(int i = 1; i < n1; ++i) {
for(int j = 1; j < n2; ++j) {
if(ch1[i] == ch2[j]) {
table[i][j] = table[i-1][j-1] + 1;
}else
table[i][j] = table[i-1][j] > table[i][j-1] ? table[i-1][j] : table[i][j-1];
}
}

return table[n1-1][n2-1];
}
}

```

```#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;
int solve(string str){
int n=str.size();
int *flag=new int[n*n];
for(int i=0;i<n*n;i++){
flag[i]=0;
}
for(int i=n-1;i>=0;i--){
flag[i*n+i]=1;
for(int j=i+1;j<n;j++){
if(str[i]==str[j])
flag[i*n+j]=flag[(i+1)*n+j-1]+2;
else
flag[i*n+j]=max(flag[(i+1)*n+j],flag[i*n+j-1]);
}
}
int res=n-flag[n-1];
return res;
}
int main(){
string s;
while(cin>>s){
cout<<solve(s)<<endl;
}
return 0;
}```

```#include<iostream>
#include<string>
using namespace std;
int main(){
string s1;
int max_len[1001][1001];
while(cin >> s1){
string s2(s1.rbegin(), s1.rend());
for(int i=0;i<=s1.length();i++)
for(int j=0;j<=s2.length();j++){
if(i==0 || j==0 )
max_len[i][j] = 0;
else if(s1[i-1] == s2[j-1])
max_len[i][j] = max_len[i-1][j-1] + 1;
else
max_len[i][j] = max(max_len[i-1][j] , max_len[i][j-1]);
}
cout << s1.length() - max_len[s1.length()][s2.length()] <<endl;
}
}```

果然还是动态规划来解释比较简单的了。。。之前自个理解错了。。很僵硬

```function Max(a,b){
return a>b?a:b;
}
function find (str1) {
var str2 = str1.split("");str2 = str2.reverse();str2 = str2.join("");
var max = 0;
var resArr = new Array(str1.length+1);
for(var i = 0;i<=str1.length+1;i++){  //初始化
resArr[i] = new Array(str2.length+1);
for(var j = 0;j<=str2.length+1;j++){
resArr[i][j] = 0;
}
}

for(var i = 0;i<=str1.length;i++){
for(var j = 0;j<=str2.length;j++){
if(i==0||j==0){
resArr[i][j] = 0;
}else{
if(str1[i-1] == str2[j-1]){
resArr[i][j] = resArr[i-1][j-1]+1;//前一次循环中数组元素保存的值加1
}else{
resArr[i][j] = Max(resArr[i-1][j],resArr[i][j-1]);//不用连续
}
}
if(max<resArr[i][j]){
max = resArr[i][j];//保存最大的数，也就是匹配最长的长度
}
}
}
//输出结果
if(max == 0){
return str1.length;
}else{
return str1.length-max;
}
}```

把输入的字符串按照中间夹杂的杂项数量分为三种情况：
2.回文之间杂项为1。例如:   goXogle(2)、abXba(0)这种。
3.回文之间杂项大于1。例如：abcda(2)、goabcogle(4)这种。
然后对应每种情况来解：
```function getCount(str){
var strArr = str.split("");
var strLen = 0;
for(var i=0;i<strArr.length;i++){
for(var j=strArr.length;j>=i;j--){
if(strArr[i]==strArr[j]){
var count = 1;
var temp_i = i,temp_j = j;
while(strArr[++temp_i]==strArr[--temp_j]){
if(temp_i<temp_j){//情况一
count++;
}else if(temp_i == temp_j){//情况二
count+=0.5;
}else{//防止死循环
break;
}
}
if(temp_j>temp_i){//情况三
count+=0.5;
}
if(count>strLen){
strLen = count;
}
}
}
}
return str.length-Math.floor(strLen*2);
}```

```import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String str =sc.nextLine();
char[] strchar = str.toCharArray();
int length= strchar.length;
int[][] dp = new int[length][length];
for(int j=1;j<length;j++){
dp[j-1][j]=strchar[j-1]==strchar[j]?0:1;
for(int i=j-2;i>-1;i--){
if(strchar[i]==strchar[j]){
dp[i][j]=dp[i+1][j-1];
}else{
dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
}
}
}
}
}
}
```

#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

//自底向顶的动态规划
intLCS(string str1, string str2, intn1, intn2)
{
vector<vector<int>> nVec(n1+1);
for(inti = 0; i < n1+1; ++i)
{
nVec[i].assign(n2+1, -1);
}
for(inti = 0; i < n2+1;++i)
{
nVec[0][i] = 0;

}
for(inti = 0; i < n1+1; ++i)
{
nVec[i][0] = 0;
}
for(inti = 1; i <= n1;++i)
{
for(intj = 1; j <= n2;++j)
{
if(str1[i-1] == str2[j-1])
{
nVec[i][j] = nVec[i - 1][j - 1] + 1;

}
else
{
nVec[i][j] = max(nVec[i][j - 1], nVec[i - 1][j]);
}
}
}
returnnVec[n1][n2];
}
intmain()
{
string str;
while(cin>>str){
string::size_type nLen = str.size();
string str1 = str;
reverse(str1.begin(),str1.end());
cout<<nLen - LCS(str,str1,nLen,nLen)<<endl;
}
return0;
}

# pyhon使用DP的解决方案

``````import sys
``````
``````def main():
for line in sys.stdin:
str1 = line[:-2]
n = len(str1)
str2 = str1[::-1]
rec = [[0 for x in range(n+1)] for x in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
if str1[j-1] == str2[i-1]:
rec[i][j] = rec[i-1][j-1] + 1
else:
rec[i][j] = max(rec[i-1][j], rec[i][j-1])
print n - rec[n][n]
main()
``````

```#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int MAX = 1001;
int MaxLen[MAX][MAX]; //最长公共子序列，动态规划求法
int maxLen(string s1, string s2){
int length1 = s1.size();
int length2 = s2.size();
for (int i = 0; i < length1; ++i)
MaxLen[i][0] = 0;
for (int i = 0; i < length2; ++i)
MaxLen[0][i] = 0;

for (int i = 1; i <= length1; ++i)
{
for (int j = 1; j <= length2; ++j)
{
if (s1[i-1] == s2[j-1]){
MaxLen[i][j] = MaxLen[i-1][j - 1] + 1;
}
else
{
MaxLen[i][j] = max(MaxLen[i - 1][j], MaxLen[i][j - 1]);
}
}
}

return MaxLen[length1][length2];
}

int main(){
string s;
while (cin >> s){
int length = s.size();
if (length == 1){
cout << 1 << endl;
continue;
}
//利用回文串的特点
string s2 = s;
reverse(s2.begin(),s2.end());
int max_length = maxLen(s, s2);
cout << length - max_length << endl;
}
return 0;
}
```

### C++ 动态规划

```#include <bits/stdc++.h>

using namespace std;

/*
dp[i][j]: i到j的最长回文子序列长度
1. s[i] = s[j], 则dp[i][j] = dp[i + 1][j - 1] + 2;
2. s[i] != s[j], dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);

*/
int main() {
string s;
int dp[1003][1003];
while (cin >> s) {
int n = s.size();
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int j = 1; j < n; ++j) {
for (int i = j - 1; i >= 0; --i) {
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
}
}
cout << n - dp[0][n - 1] << endl;
}
return 0;
}```

```import java.io.BufferedReader;
import java.io.IOException;

public class Main {
public static void main(String[] args) throws IOException {
String str1;
// 最长回文串的长度其实就是原串及其反转串的最长公共子串的长度（无需连续），原串长度减去这个长度就是要删除的字符数
while((str1 = br.readLine()) != null) {
String str2 = new StringBuilder(str1).reverse().toString();
int n = str1.length();
int[][] dp = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
dp[i][j] = str1.charAt(i - 1) == str2.charAt(j - 1)? dp[i - 1][j - 1] + 1: Math.max(dp[i - 1][j], dp[i][j - 1]);
}
System.out.println(n - dp[n][n]);
}
}
}```

```public static int maxLen(String str) {
StringBuilder sb1 = new StringBuilder(str);
StringBuilder sb2 = new StringBuilder(str).reverse();
int len = str.length();
int[][] maxLen = new int[len + 1][len + 1];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++) {
if (sb1.charAt(i - 1) == sb2.charAt(j - 1))
maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
else
maxLen[i][j] = Math.max(maxLen[i - 1][j], maxLen[i][j - 1]);

}
}
return len - maxLen[len][len];
}```

``````/* 做题需要脑子，多分析思考。。
* 多思考，问题会很简单。。。。
* 数学分析。。。。。。。。。。
*/
#include<stdio.h>
char s[1000];
int a[1000][1000];

int min( int x, int y)
{
return x<y?x:y;
}

//递归时间复杂度太高了，改用动态规划
int func( int begin, int end)
{
int i, k;
for( k=1; k<end-begin+1; k++)
{
for( i=begin; i<end; i++)
{
if( s[i]==s[i+k]) a[i][i+k]=a[i+1][i+k-1];
else a[i][i+k] = min( a[i][i+k-1], a[i+1][i+k])+1;
}
}
return a[begin][end];
}

int main()
{
int i=0, j, flag=0; char c;

while(1)
{
for( i=0; (c=getchar())!=EOF; i++)
{
if( c=='\n') break;
s[i]=c;
}
if( c==EOF) break;
printf( "%d\n", func( 0, i-1));
}

return 0;
}
``````

```#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int solution(string s){
int result;
int n=s.length();
int dp[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dp[i][j]=0;
}
}
for(int j=0;j<n;j++){
dp[j][j]=1;
}
for(int j=1;j<n;j++){
for(int k=0;k<n-j;k++){
if(s[k]==s[k+j]){
dp[k][k+j]=dp[k+1][k+j-1]+2;
}
else{
dp[k][k+j]=max(dp[k+1][k+j],dp[k][k+j-1]);
}
}
}
result=n-dp[0][n-1];
return result;
}
int main(){
string s;
while(cin>>s){
cout<<solution(s)<<endl;
}
return 0;
}```

#include<bits/stdc++.h>
using namespace std;

int getGGZC(string s1,string s2){
vector<vector<int>> ss(s1.size(),vector<int>(s2.size(),0));

//初始化 如s1="abc" s2="acdeeee"。s1和s2首字母相等则
//ss[0][0](a,a)，ss[0][1](a,ac)，ss[0][2](a,acd)...
//ss[1][0](a,a),ss[2][0](ab,,a),ss[3][0](abc,a)...等最长公共子串都是1.
//首字母不等则都为0.
if(s1[0]==s2[0]){
for(int i=0;i<s1.size();i++){
ss[i][0]=1;
}
for(int j=0;j<s2.size();j++){
ss[0][j]=1;
}
}

//i,j分别表示s1和s2上字符的位置
//如 s1="abc" s2="acdeeee" ss[1][2]的值就是“ab”和“acd”的最大公共子串长
for(int i=1;i<s1.size();i++){
for(int j=1;j<s2.size();j++){
if(s1[i]==s2[j])ss[i][j]=ss[i-1][j-1]+1;
else{
ss[i][j]=max(ss[i-1][j],ss[i][j-1]);
}
}
}
int a=ss[s1.size()-1][s2.size()-1];

return a;

}

int main(){
string str;
while(cin>>str){

string ss=str;
reverse(ss.begin(),ss.end());

cout<<ss.size()-getGGZC(str,ss)<<endl;
}

return 0;
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;

intmain(){

string str;
while(cin >> str){
string s1(str);
string s2(str.rbegin(),str.rend());
intlen = s1.size();
vector< vector<int> >lcs(len+1,vector<int>(len+1,0));
/*
for(int i = 0; i < len+1;++i){
lcs.at(i).at(0) = 0;
}
for(int i = 0; i < len+1; ++i){
lcs.at(0).at(i) = 0;
}
*/
for(inti = 1; i <= len; ++i){
for(intj = 1; j <= len; ++j){
if(s1.at(i-1) == s2.at(j-1)){
lcs.at(i).at(j) = lcs.at(i-1).at(j-1) + 1;
}
else{
lcs.at(i).at(j) = max(lcs.at(i).at(j-1), lcs.at(i-1).at(j));
}

}
}

cout<< len - lcs.at(len ).at(len)<<endl;

}

return0;

```import java.util.*;
public class Main{
public static void main(String[] arg){
Scanner input = new Scanner(System.in);
while(input.hasNextLine()){
String s = input.nextLine();
char[] c = s.toCharArray();
intlen  = c.length;
int[][] state = new int[len+1][len+1];
state[0][0] = 0;
for(int i = 0; i < len; i++){   //正序的每一个字符同反序的每一个字符比较
for(int j = 0; j < len; j++){
if(c[i] == c[len-1-j]) state[i+1][j+1] = state[i][j] + 1;  //字符是相同的  则前一个字符相同的数加一
else state[i+1][j+1] = Math.max(state[i+1][j],state[i][j+1]); //对应的字符不相同  则取前面相同字符数中最大那个
//这样得到就是相同字符数最多的值  就是回文的长度  总长减去此长  就得到要删减的数目
}
}
System.out.println(len - state[len][len]);
}
}
}
```

168条回答 52265浏览

## 通过挑战的用户

• 2023-03-14 14:28:22
• 2023-02-28 15:53:05
• 2023-02-26 16:02:47
• 2023-02-11 20:46:05
• 2023-02-11 17:28:58

## 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题